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

learn more… | top users | synonyms

1
vote
0answers
34 views

Solving a Knapsack problem with a special structure

I have a set of $N$ items to fill a knapsack with maximum capacity $W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following: max ...
2
votes
1answer
58 views

Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
-1
votes
0answers
33 views

Minimizing the walking distance between walkways

I have the following problem: You are helping to design a new airline terminal. The terminal will have an extremely long hallway, and passengers will have to travel from one end to the other. To ...
0
votes
0answers
18 views

Particle locating/collision prediction in bounded (two-dimensional) environments

I believe that many physics engines, particle simulators, and even video games use discrete-event simulation to determine where a particle or object is at any moment, and the direction in which it is ...
6
votes
2answers
99 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
0
votes
0answers
28 views

Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to ...
2
votes
1answer
33 views

What is the formal justification for the correctness of the second formulation of rod cutting DP solution

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference. Define $r_j$ to be the optimal way to cut a rod ...
2
votes
1answer
36 views

Orderability of Belief States in a POMDP?

Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states. It seems reasonable to think that belief states for this POMDP may be ...
1
vote
0answers
24 views

Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
3
votes
1answer
32 views

Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
2
votes
3answers
185 views

Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem: We are given a ...
1
vote
1answer
45 views

Is it possible to solve the coin denomination problem using a 1-D array?

In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed: Exercises 8.4 #9 Is it not possible to do this using a 1-D array. I ...
1
vote
1answer
27 views

Shuffled Strings Dynamic Programming [closed]

So I have this question: A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. Example would be ...
2
votes
1answer
105 views

Trying to understand this Dynamic Programming solution

The problem is as follows. Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq ...
2
votes
1answer
22 views

First Harshad number with given sum

How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits. I think that some kind of dynamic ...
1
vote
1answer
50 views

What type of knapsack problem is this?

I need to choose the highest value combination of items given a specific set of constraints. These constraints are: Exactly 6 items from group A and 2 items from group B must be selected. Items in ...
3
votes
1answer
84 views

Tile Problem : Dynamic Programming

Came across the following tile problem : ...
3
votes
2answers
122 views

Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$. $M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$ ... $M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$ ...
1
vote
1answer
46 views

Check if a tree is formed by 3 subtrees with given number of nodes

I have run into a contest problem (ACM like) that sounds like this: Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$ Question: Can the tree be partitioned into three trees of $X,Y,Z$ ...
14
votes
3answers
469 views

Largest sum divisible by n

I asked this question on StackOverflow, but I think here is a more appropriate place. This is a problem from Introduction to algorithms course: You have an array $a$ with $n$ positive integers ...
3
votes
0answers
36 views

How to compare A* with DP approach in finding shortest Path?

Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a ...
0
votes
1answer
27 views

DP - Removing contiguous subsequences from a sequence optimally

I was asked this question a while ago and I'm very stuck: You have a sequence of 0's and 1's, and you can perform one ...
0
votes
0answers
37 views

Longest double increasing subsequence (LIS variant)

I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each ...
3
votes
1answer
96 views

Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
6
votes
2answers
690 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 ...
3
votes
1answer
79 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
36 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
62 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
65 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
148 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
46 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 ...
5
votes
0answers
108 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
114 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
39 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
205 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
21 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
56 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
162 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
38 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
58 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
54 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
19 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
130 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
91 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
24 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
71 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
262 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$ ...
5
votes
1answer
132 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
52 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 ...