How does dynamic programming work
Have you ever computed Fibonacci numbers with recursion? To get fib(5), you call fib(4) and fib(3), and fib(4) in turn calls fib(3) and fib(2). But fib(2) keeps showing up again, here and there. You end up solving the same thing over and over. What if you wrote down each answer the first time you solved it?
Solving the same thing again
Recursion solves a big problem by splitting it into smaller ones, and Fibonacci is a perfect example.
fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) and fib(2). Look closely, though, and fib(2) keeps turning up on one branch after another.
Press a node in the tree below to check.
The same small problem shows up all over the tree. (click a node → every node with the same value lights up)
The same fib(2) is solved not once but several times, and the same goes for fib(3).
As n grows, this duplication swells alarmingly.
Solving an answer you've already worked out again and again is plainly wasteful.
Write the answers down
The fix is surprisingly simple: write each answer on a note once you've solved it.
The next time you need the same thing, don't recompute it; just take it from the note. Compute only what you're seeing for the first time, and reuse anything you've seen before.
Press the button to handle the calls one at a time.
Compute and write down what's new, and take from the note what you've seen before. This is memoization.
Each value is computed only once, the first time. Everything else comes straight from the note, so solving the same thing twice disappears entirely.
Writing down solved answers and reusing them like this is called memoization.
The name sounds grand, but at heart it's just "writing it down."
Filling a table from the bottom up
You can also run the same idea in reverse. Instead of splitting from the top down, you fill a table upward, starting from the smallest values at the bottom.
You simply know fib(0) and fib(1). Add those two to get fib(2), then add fib(1) and fib(2) to get fib(3).
Since the cells below are already written, each cell above is just an addition.
Fill upward one cell at a time, starting from 0,1. (next cell = sum of the two cells just below · bottom-up)
This way doesn't even need a separate note, because the table itself is the note.
Sweep once from bottom to top, in order, and there's never anything to solve again.
If memoization is "write it down when you need it," this is "write it all down in advance." The underlying idea is the same.
Dramatically faster
So how much faster does it get? Just writing things down makes an enormous difference.
Plain recursion solves even the duplicates, so its workload explodes as n grows. With memoization, each cell is solved exactly once, so the work grows only in proportion to n.
Grow n and compare the two, and the gap jumps out.
The number of solves at the same n. (plain recursion = explodes exponentially · memo = linear, proportional to n)
Even when n grows only a little, the plain recursion bar shoots up as if to burst through the screen, while the memo bar barely moves.
Not solving the same answer twice: that one thing is what separates slow from fast.
Summary
Dynamic programming has a difficult name, but at heart it's three steps.
Notice that you're solving the same thing again, write down each answer once you've solved it, and reuse it, and things get dramatically faster.
Press the cards below one by one to sum up the three steps.
Solving the same thing again → writing it down → dramatically faster. It also recalls why divide and conquer, whose pieces never overlap, had no need to write anything down.
In divide and conquer, which we saw earlier, the pieces never overlapped, so there was nothing to write down.
That's exactly the fork in the road. When pieces overlap, in other words when the same small problem keeps coming back, the single move of writing things down changes everything.