Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

learn more… | top users | synonyms

0
votes
0answers
48 views

Dynamic Programming problem: A number as a sum of squares

Following is the problem I am trying to solve: Problem Statement Find the number of $n$-tuples $(a_1,a_2,a_3,\cdots,a_n)$ such that ...
-2
votes
1answer
28 views

Using dynamic programming to find the number ofl increasing subsequences

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
0
votes
0answers
19 views

Dynamic programming: finding recursive rules [closed]

I'm struggling with studying dynamic programming. I understood the principle behind it (a recursion in a problem which exhibit optimal substructure) and I can solve some easy ones but only after I ...
0
votes
2answers
62 views

Minimal length of a string that contains two strings

We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this ...
0
votes
1answer
16 views

How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution. Is there any approach to the knapsack problem that does not require ...
3
votes
0answers
58 views

2D version of LeetCode house robber problem

The house robber problem of leetcode can be described as followed : A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the ...
2
votes
1answer
29 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
-1
votes
0answers
33 views

A Dynamic Programming problem

I need help in solving the following problem: Given are 'N' pipes which have threads at both ends. The front thread of a pipe is a cylinder which can fit into the rear thread of some other pipe. ...
1
vote
0answers
29 views

Minimum vertices to cover other vertices with max weight [duplicate]

I have a problem where I'm given the input of a graph. The output would be a set of vertices such that I have the minimum number of vertices to cover other vertices and if there is more than one ...
1
vote
1answer
26 views

Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
1
vote
0answers
16 views

Finding max average value subrectangle at least a certain size in a 2-d sparse array

So Kadane's dynamic programming solution for finding the maximum sum contiguous subinterval in a 1-d array runs in linear time, and can be adapted to give a best-known $O(m^2n)$ time solution to find ...
0
votes
1answer
54 views

Binary tree node value maximization

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be ...
1
vote
0answers
41 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
1answer
34 views

Integer Knapsack Problem - No duplicates Allowed

In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given ...
0
votes
0answers
25 views

Weighted Interval Scheduling with constraint

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do ...
0
votes
2answers
211 views

Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

http://www.algorithmist.com/index.php/UVa_10918 The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the ...
0
votes
0answers
75 views

Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?

Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time. We can have a matrix : dp[s][i][j] : which computes ...
7
votes
3answers
1k views

Efficient algorithm for this optimization problem? Dynamic programming?

I've created a diagram that depicts what I'm trying to accomplish. Full-size Image In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to ...
2
votes
1answer
43 views

A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
1
vote
1answer
59 views

Practical applications of Weighted Independent Set in path graph?

Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path. Does this problem have practical applications? What are some? This problem is used in ...
0
votes
0answers
33 views

Utility Maximizing Challenging Assignment Problem

There is a grid of size MxN. M~20000 and N~10. So M is very huge. So one way is to look at this is N grid blocks of size M placed side by side. Next assume that there are K number of users who each ...
0
votes
1answer
73 views

Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
2
votes
1answer
56 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
0
votes
1answer
50 views

Shortest path in a matrix

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each ...
5
votes
1answer
202 views

Solving road trip problem in linear time

Consider the following problem: You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between ...
0
votes
0answers
72 views

Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
-2
votes
1answer
77 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
0
votes
0answers
22 views

Regarding number of iterations in Value Iteration

In value iteration for single goal problem, does the number of iterations it takes for the convergence to terminate dependent on grid world size, or discount factor or threshold set or none of the ...
0
votes
0answers
31 views

Dynamic programming in the direction of path planning

I have been doing literature survey for a dynamic programming project. And I have found several good references of research work in the fields of learning and control viz. reinforcement learning and ...
1
vote
2answers
269 views

Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid. The only possible moves are right and up. Also, you can't move below the diagonal y=x. e.g if you're at ...
1
vote
1answer
110 views

Longest Common Subsequence Via Dynamic Programming

I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original ...
4
votes
1answer
89 views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
-1
votes
1answer
73 views

Dynamic Programming - Adding up N Integers

I'm studying for a final and the professor gave us a practice problem to prepare, but it's extremely difficult and I've been hacking at it for hours with no luck. Here it is: It's driving me ...
0
votes
0answers
87 views

Dynamically weighted priority queue?

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value ...
1
vote
2answers
108 views

Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
3
votes
1answer
269 views

What is a naive method?

I was researching dynamic programming and read the following: Often when using a more naive method, many of the subproblems are generated and solved many times. What is a naive method?
2
votes
2answers
259 views

Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

I'm learning Dynamic Programming (By myself) and in the textbook there is this question: Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight ...
1
vote
2answers
236 views

Dynamic programming to find the least possible balance of a full binary tree

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
1
vote
1answer
203 views

Dynamic Programming Subset Sum Problem with twist

Question: You are given an input , which is a sequence of positive integers $w_1, w_2, . . . , w_n$ with parameters $W, ∆. $We wish to find $S ⊆ \{1, 2, . . . , n\}$ such that $\sum_{j \in S} w_j$ is ...
1
vote
1answer
32 views

Black box with O(n) calls

Let's say a procedure called 'decision(x,q)' is available as a 'black box' X is the input set and Q is a real number Q. I need to design an algorithm that reports "yes" if there exists a subset of X ...
4
votes
1answer
494 views

Is CYK still relevant today?

I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today. Is it or an extension of it still being used in compilers (for example), or have other ...
2
votes
1answer
72 views

Solving a dynamic programming problem?

Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down? My one friend said to me that this problem can be ...
2
votes
0answers
20 views

Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...
2
votes
0answers
31 views

Training a model to match two time series

Context I have two related time series, I want to learn to produce one from the other. However, they aren't synchronous, and the lag between the two does not revert to the mean, it accumulates. ...
-2
votes
1answer
66 views

Dynamic Programming Approach

when we are trying to solve a problem with dynamic programming. we have to follow some general steps characterize the solution structure Recursively define optimal solution compute the value from ...
4
votes
1answer
479 views

Computing the mode of XOR subsequences

I was confronted with this problem in an online programming challenge and it has been bugging me since: In the problem, you are given a list of 16-bit numbers, say $a_0, a_1, ..., a_n$. An "XOR ...
2
votes
2answers
217 views

Segmenting an English string with no spaces using dynamic programming

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as ...
2
votes
0answers
131 views

Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
5
votes
1answer
239 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
4
votes
1answer
216 views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...