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

learn more… | top users | synonyms

6
votes
2answers
559 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
-2
votes
0answers
31 views

Dynamic programming riddle

In the room there are 100 boxes numbered from 1 to 100. David has 100 cards numbered also from 1 to 100. He randomly puts each card in a random box. Student A enters the room and can see all the cards ...
2
votes
1answer
57 views

Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
1
vote
1answer
27 views

Travelling plan between two places

There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$. At each step $i$ there are two choices: stay where you are or ...
3
votes
1answer
39 views

Proof for Minimum number of insertions to convert a string to a palindrome

For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is: $$ c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = ...
1
vote
1answer
37 views

Number of submatrices, of a base matrix derived from an array, with a particular sum

Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its ...
3
votes
1answer
110 views

Find a maximum sum in matrix, subject to special constraint

I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in ...
3
votes
1answer
38 views

Remove contiguous subsequence so the remaining numbers will created a sorted sequence

You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then ...
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
4
votes
0answers
77 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x ...
1
vote
0answers
79 views

Dynamic programming: speed of top down vs bottom up approaches

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...
0
votes
1answer
28 views

Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?

why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire ...
6
votes
0answers
105 views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
1
vote
0answers
20 views

Dynamic programming: maximize the number of things to be bought

For example, for a product, we have a list of the number of products you buy and the corresponding price you pay with this number of products: number = {1, 5, 8, 12} price = {0.5, 2, 3, 3.6} (i.e. ...
-1
votes
1answer
41 views

Check if a string can be split into two subsequences

Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y. Example: ...
-1
votes
1answer
87 views

How to balance parentheses/brackets in a string with minimum cost?

Given a word composed of opening and closing parentheses and brackets, we can do two operations: Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This ...
0
votes
1answer
27 views

How does Hassin's algorithm for the Restricted Shortest Path work?

I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds ...
2
votes
1answer
50 views

Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base), -1 gap penalty and -1 for a mismatch. Given two ...
0
votes
1answer
41 views

What is the difference between dynamic programming and a mere caching?

I mean why should we use such epic buzzword when you can say: "cache your results!".
0
votes
0answers
18 views

How to apply recursion in this problem [duplicate]

Problem Statement : You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one ...
1
vote
1answer
72 views

Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying ...
1
vote
0answers
67 views

A variant of coin change problem

Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in ...
0
votes
1answer
21 views

Optimized resource allocation problem

I am from ECE background and trying to solve channel allocation problem. Let's assume I have three users and three available channels. I would like to allocate channel among them in such a way that ...
2
votes
0answers
58 views

Given a set of integers $S$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time

Given a set of integers $S=\{s_1,s_2,...,s_n\}$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time. I am not quite sure how to solve this but I think I have the ...
2
votes
1answer
115 views

Using dynamic programming to maximize work done

Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ ...
6
votes
1answer
122 views

A variant of the vertex cover problem on trees

Consider the following variation on the vertex cover problem: given a tree on $n$ vertices, we are asked to calculate minimum size of a multiset $S$ such for each edge $(u,v)$ in the tree at ...
1
vote
1answer
34 views

Minimum number of rounds to notify a hierarchy of people with DP

I'm trying to figure out a problem reported in Kleinberg (ch 6 no.16). I know that there are solutions based on ordering, anyway i'd like to understand if another way exists. Basically, we have a ...
3
votes
0answers
89 views

When not to use dynamic programming

I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the ...
2
votes
1answer
56 views

Binomial coefficient to approach multi-way choices DP problem?

I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not homework: i've already a solution, just considering if i'm ok with the theory. ...
3
votes
1answer
69 views

Easiest improvement on first-fit for bin packing algorithm

See the interactive example here. First-fit on the left, optimal on the right. I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the ...
0
votes
0answers
10 views

method of proving solution with dynamic programming [duplicate]

Is there any method of proving solution with dynamic programming ? Maybe induction ? I don't have idea. Help me please.
21
votes
4answers
3k views

What is dynamic programming about?

Sorry in advance if this question sounds dumb... As far as I know, building an algorithm using dynamic programming works this way: express the problem as a recurrence relation; implement the ...
2
votes
1answer
145 views

Maximum independent nodes subset algorithm with strong constraint

I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints: The selected nodes must be the optimal solution (maximal sum of weight). If one node is ...
-4
votes
1answer
153 views

NUMBER OF WAYS TO GET XOR OF n NUMBERS TO BE 0

Alice and Bob are playing the game of Nim with $n$ piles of stones (p[0], p[1], ..., p[n-1]). If Alice plays first, she loses if and only if the 'xor sum' (or 'Nim sum') of the piles is zero, i.e. ...
3
votes
0answers
114 views

Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
0
votes
0answers
65 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins. I came into the following formula: $$ T(n,S) = ...
3
votes
1answer
352 views

Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
1
vote
1answer
214 views

Dynamic Programming Travel Planning Problem

You want to visit n cities: $0 → 1 → 2 → · · · → n$. For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes of transportation: train or plane. You are ...
4
votes
1answer
52 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
-2
votes
1answer
71 views

Using dynamic programming to find the number ofl increasing subsequences [closed]

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
2answers
80 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 ...
1
vote
1answer
48 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 ...
4
votes
0answers
164 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 ...
3
votes
1answer
55 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
vote
0answers
30 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
98 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
82 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
66 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
48 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
108 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 ...