Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
13
votes
2answers
13k views

When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
39
votes
3answers
15k views

Deciding on Sub-Problems for Dynamic Programming

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
33
votes
4answers
4k 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 ...
52
votes
3answers
22k views

Knapsack problem — NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
19
votes
6answers
13k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. ...
3
votes
1answer
1k 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$ ...
5
votes
2answers
8k views

Proof of an Optimal substructure in Dynammic Programming?

Could someone please explain how exactly the proof of optimal substructure property in dynamic programming problems works? They usually say: Let's say the global optimal solution is A, and B is ...
11
votes
1answer
11k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $...
11
votes
2answers
4k views

Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
15
votes
3answers
12k views

dynamic programming exercise on cutting strings

I have been working on the following problem from this book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves ...
3
votes
3answers
2k views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
4
votes
1answer
485 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
3
votes
2answers
2k views

Dynamic programming table for finding similar substrings is too large

Substring Diff Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}...
1
vote
2answers
105 views

Given matrix, count paths visiting each number exactly once

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
1
vote
2answers
487 views

Broken stick problem

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible. The amount of glue need to connect ...
33
votes
2answers
9k views

Is there a difference between top-down and bottom-up dynamic programming?

Is there a fundamental difference between top-down and bottom-up dynamic programming? In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach ...
14
votes
3answers
1k views

Memoization without array

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow: A memoized recursive algorithm maintains an entry in a table for the ...
12
votes
2answers
14k 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 ...
12
votes
2answers
587 views

Matrix chain multiplication and exponentiation

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}...
19
votes
5answers
2k views

A Case Distinction on Dynamic Programming: Example Needed!

I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See ...
9
votes
1answer
3k 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$ ...
0
votes
0answers
58 views

How to solve this dynamic programming puzzle on matrix?

We are given 4 integers N,M ,Q and Z. Initially,the matrix has all zeroes in it. We have to perform Q operations on the matrix. In each operation, any cell of the matrix can be selected(same cell ...
9
votes
4answers
3k views

What is “dynamic” about dynamic programming?

One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called ...
3
votes
1answer
1k views

Domino and Tromino Combined Tiling

If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible? I am aware that when only 2x1 dominoes are used ...
3
votes
1answer
461 views

Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
7
votes
2answers
868 views

Dynamic programming algorithms with log in the run-time

Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?
4
votes
1answer
375 views

Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties: optimal substructure overlapping subproblems I stumbled upon an article which ...
3
votes
1answer
3k views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
3
votes
0answers
818 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: ...
2
votes
1answer
249 views

Lexicographically smallest down-right path in matrix

Here is the problem which I thought was simple dynamic programming, which is however not the case. Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
2
votes
2answers
1k views

How to use dynamic programming to solve this?

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
2
votes
0answers
73 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
2answers
4k views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
1
vote
1answer
1k 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
1answer
514 views

Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing. I am working on the following problem: Suppose you are consulting ...
-1
votes
1answer
141 views

To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

This problem is from codechef.Can anyone please help me out with this one as I am unable to find out the subproblem.Thanks in advance! Problem -: In IPL 2025, the amount that each player is paid ...
4
votes
1answer
2k views

Algorithm for splitting array into subarrays with sums close to the target value

I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$. Let $s(A)$ denote the sum of elements of array $A$. I also have an integer $t$, such that $1 < t \le s(A)$. I want to split the ...
4
votes
1answer
1k 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 ...
4
votes
2answers
2k 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 ...
3
votes
1answer
268 views

Request for examples to show various types of subproblems in dynamic programming

Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are prefix/postfix of a string/sequence/...
2
votes
0answers
75 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
2
votes
2answers
521 views

Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
1
vote
1answer
1k 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
1answer
909 views

How can you determine what set of boxes will maximize nesting?

I'm trying to find a dynamic solution to the nesting boxes problem. You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
1
vote
1answer
26 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
1
vote
0answers
710 views

Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
0
votes
0answers
252 views

Dynamic programming problem — Finding a suitable algorithm

Bob has $2$ cranes and $M$ available containers ($1 \leq C_i \leq M$) and he has to do $N$ transports from one container to another given an input list (the order of the transports must be respected). ...