# Questions tagged [dynamic-programming]

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

64 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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....
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 ...
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. ...
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 ...
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$ ...
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 ...
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 ...
1answer
14k views

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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
2answers
716 views