Nib asked for
When the Trick Applies
Dynamic programming works when a problem has overlapping subproblems (the same smaller questions keep recurring) and optimal substructure (the best overall answer is assembled from best answers to smaller pieces).
6 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1two properties
By now you have seen the trick twice: remember answers, or fill a table. But it is not magic, and it does not rescue every recursive problem. It needs the problem to have a particular shape, and two properties describe that shape. Learning to spot them tells you when to reach for it.
The trick only works on problems with a particular shape, and two properties name it.
a common mix-upDynamic programming is a trick that speeds up any recursive function.
2overlap
The first property is overlapping subproblems: while solving the big problem, the same smaller questions come up again and again. Fibonacci is the example you know. Computing fib(5) asks for fib(3) in two different places, and fib(2) in three. Because the questions repeat, a saved answer gets reused, and that reuse is where all the savings come from.
Overlapping subproblems: the same smaller questions keep coming back, so saved answers get reused.
In a call tree where every subproblem appeared only once, would remembering answers help?
Show the answer
No. A saved answer would never be reused, so you would gain nothing.
3no overlap
To see the contrast, picture sorting a list by splitting it in half and sorting each half. Each half is a different piece of the list, and no half is ever asked about twice. There is nothing to reuse, so a memory table would just sit there unused. Recursion alone is the right tool there. Overlap is what makes remembering worth the effort.
If subproblems never repeat, memory buys nothing; plain recursion is enough.
a common mix-upAny problem that splits into smaller problems benefits from memoization.
4best from best
The second property is optimal substructure: the best answer to the whole problem can be built from the best answers to its smaller pieces. This is what lets you trust a saved answer. If you remember the best result for a smaller piece, you can drop it into the larger problem without ever revisiting how you got it. Fibonacci has a trivially simple version, since each value is just built from two smaller values.
Optimal substructure: best answers to small pieces combine into the best answer to the whole.
5swap argument
Here is a concrete case. Suppose the cheapest route from A to C passes through B. Then the A-to-B part of that route must itself be the cheapest way to get from A to B, because a cheaper A-to-B path would make the whole trip cheaper too. So the best whole is made of best parts. Some problems break this rule: if a choice in one piece can spoil what is possible in another, a best piece no longer guarantees a best whole.
If the best whole contains a worse piece, you could swap in a better piece, so best wholes use best pieces.
If the best route A to C goes through B, could its A-to-B part be a costly detour?
Show the answer
No. Replacing it with a cheaper A-to-B path would make the whole route cheaper, contradicting that it was best.
6the checklist
So the test has two questions. Do the same smaller questions keep recurring? And can a best overall answer be assembled from best smaller answers? If both are yes, dynamic programming fits, and you can remember or tabulate with confidence. If the first is no, plain recursion will do. If the second is no, saved answers can't be trusted to combine. Next page puts the test to work on a brand-new problem.
Two yes answers (recurring questions, best-from-best) mean dynamic programming fits.
Dynamic programming isn't a cure for slow recursion; it's a match between a trick and a shape. Spot recurring questions and best-from-best pieces, and you know the trick will work.