Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
14
votes
2answers
14k 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 ...
35
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 ...
40
votes
3answers
17k 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....
60
votes
3answers
28k 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
15k 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
2k 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
2k 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$ ...
4
votes
2answers
10k 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
2answers
23k 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 ...
11
votes
1answer
14k 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 ...
17
votes
3answers
15k 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
3k 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
594 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
1answer
840 views

DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
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
1answer
193 views

Minimum cost of “signal” cover in a tree with DP

I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
1
vote
2answers
537 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 ...
0
votes
2answers
177 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 ...
34
votes
2answers
12k 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
2k 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 ...
11
votes
4answers
4k 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 ...
10
votes
1answer
4k 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$ ...
13
votes
2answers
716 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 ...
10
votes
1answer
914 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
2
votes
1answer
2k views

Counting number of paths between two vertices in a DAG

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
0
votes
0answers
85 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 ...
5
votes
2answers
663 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 ...
4
votes
0answers
88 views

Assign n people to m rooms of different sizes, such that noone is alone

I'm looking for an efficient way to assign n people to m rooms in a very specific way. INPUT: The program receives two sets of people (set of males and set of females), as well as a set of available ...
3
votes
1answer
739 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
900 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
357 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/...
3
votes
0answers
970 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: ...
3
votes
0answers
413 views

Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
3
votes
1answer
4k 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 ...
2
votes
1answer
582 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
0answers
82 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). ...
2
votes
2answers
2k views

Find minimum number of time points that cross out all intervals

Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of ...
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
1answer
202 views

(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

The following question is taken from Leetcode entitled 'Combination Sum' Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
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
2k 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
502 views

Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
1
vote
1answer
2k 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
219 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 ...
6
votes
0answers
81 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
5
votes
1answer
3k 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
2answers
1k views

Technique for converting recursive DP to iterative 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 <...
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 ...