Stack Overflow
Stack Overflow

Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems which have recursive structure with many overlapping subproblems. Do NOT use this tag for general "dynamic" behavior in code.

The link between dynamic programming and recursion is actually very strong.

Any dynamic programming solution can be transformed into a recursive solution (with memoization), with identical performance characteristics, e.g O(n*n). The difference is primarily one of presentation.

In order to be amenable to dynamic programming, the formulation of a problem must have the optimal substructure property.

The longest common subsequence problem is a good example of a problem that can be solved with dynamic programming.

5596 questions
356
votes
12 answers

What is the difference between memoization and dynamic programming?

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?
Sanghyun Lee
  • 21,644
  • 19
  • 100
  • 126
291
votes
10 answers

What is dynamic programming?

What is dynamic programming? How is it different from recursion, memoization, etc? I have read the wikipedia article on it, but I still don't really understand it.
unknown
269
votes
9 answers

What is the difference between bottom-up and top-down?

The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems. The top-down consists in solving the problem in a "natural…
Guest
  • 3,097
  • 5
  • 20
  • 16
235
votes
21 answers

How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
Tony
  • 2,503
  • 4
  • 16
  • 7
215
votes
10 answers

Difference between Divide and Conquer Algo and Dynamic Programming

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms? How are the two terms different? I do not understand the difference between them. Please take a simple example to explain any difference between the two…
saplingPro
  • 20,769
  • 53
  • 137
  • 195
151
votes
8 answers

Throwing cats out of windows

Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of…
AndrewF
  • 6,852
  • 7
  • 29
  • 27
116
votes
5 answers

Why is the knapsack problem pseudo-polynomial?

I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits required to encode the input). Unfortunately I did not…
Michael
  • 41,026
  • 70
  • 193
  • 341
113
votes
20 answers

Find common substring between two strings

I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails. So if I have 2 strings: string1 = "apples" string2 = "appleses" answer = "apples" Another example, as the string could have more than one word: string1 =…
NorthSide
  • 1,459
  • 2
  • 12
  • 16
98
votes
5 answers

A simple example for someone who wants to understand Dynamic Programming

I am looking for a manageably understandable example for someone who wants to learn Dynamic Programming. There are nice answers here about what is dynamic programming. The fibonacci sequence is a great example, but it is too small to scratch the…
Khaled Alshaya
  • 94,250
  • 39
  • 176
  • 234
85
votes
4 answers

What is the minimum cost to connect all the islands?

There is a grid of size N x M. Some cells are islands denoted by '0' and the others are water. Each water cell has a number on it denoting the cost of a bridge made on that cell. You have to find the minimum cost for which all the islands can be…
vaibhavatul47
  • 2,766
  • 4
  • 29
  • 42
70
votes
5 answers

What's the difference between recursion, memoization & dynamic programming?

Related question: Dynamic programming and memoization: top-down vs bottom-up approaches I have gone through a lot of articles on this but can't seem to make sense of it. At times recursion and dynamic programming looks the same and at others…
Sakibul Alam
  • 1,731
  • 2
  • 21
  • 40
66
votes
9 answers

Find the number of occurrences of a subsequence in a string

For example, let the string be the first 10 digits of pi, 3141592653, and the subsequence be 123. Note that the sequence occurs twice: 3141592653 1 2 3 1 2 3 This was an interview question that I couldn't answer and I can't think of an…
Jake
  • 661
  • 1
  • 6
  • 5
66
votes
11 answers

Getting the submatrix with maximum sum?

Input: A 2-dimensional array NxN - Matrix - with positive and negative elements.Output: A submatrix of any size such that its summation is the maximum among all possible submatrices. Requirement: Algorithm complexity to be of O(N^3) History: With…
guirgis
  • 1,133
  • 2
  • 14
  • 17
61
votes
1 answer

How to count integers between large A and B with a certain property?

In programming contests, the following pattern occurs in a lot of tasks: Given numbers A and B that are huge (maybe 20 decimal digits or more), determine the number of integers X with A ≤ X ≤ B that have a certain property P SPOJ has lots of tasks…
Niklas B.
  • 92,950
  • 18
  • 194
  • 224
59
votes
4 answers

Is there a generic way to memoize in Scala?

I wanted to memoize this: def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2) println(fib(100)) // times out So I wrote this and this surprisingly compiles and works (I am surprised because fib references itself in its declaration): case class…
pathikrit
  • 32,469
  • 37
  • 142
  • 221
1
2 3
…
99 100