Dynamic programming
Dynamic programming is one observation with an unhelpful name. The observation: if the same smaller problem keeps coming back, work it out once and write the answer down. The name was chosen in the 1950s because it sounded impressive to the people holding the budget, and it has been confusing students ever since.
Press play. The tree below is fib(6) worked out the direct way, and it takes 25 calls. Watch how often the same small number appears: one of them is worked out 8 separate times, on different branches, each time from scratch.
Then press fib-memo, which is the same function with three lines added. Same number, same answer, 11 calls. Nothing was made faster. Things simply stopped happening twice.
1function fib(k) {2 if (k <= 1) return k34 return fib(k - 1) + fib(k - 2)5}
The call tree
every call splits again, however many times it has been made before
The subproblems
one slot each, and how much work it has cost
Times worked out
- ·
- ·
- ·
- ·
- ·
- ·
- ·
0 calls so far
Working out fib(6) the direct way, remembering nothing between calls.
What the repeats in the tree mean, what the table takes away, and when it takes away nothing.
What the tree is really saying
Every node is labelled with the subproblem it is solving, and that is the only label it needs, because two nodes carrying the same number are the same work being done twice. Run the plain version and the tree is full of repeats: the lower you look, the more of them there are.
That is overlapping subproblems, and it is the condition the whole technique depends on. The branches under any call are not separate problems, they are two views of almost the same problem, and a plain recursion has no way to notice.
The collapse
Now watch fib-memo. When a call is asked for a second time, it does not split. It appears faded, already holding its answer, and the entire subtree that would have grown beneath it never happens.
That is the thing worth understanding about memoisation: the saving is never one call. It is that call, and everything it would have gone on to ask for, and everything under that. At 6 the table is read 4 times and the tree goes from 25 nodes to 11. At 14 the plain version would need 1,219 calls and the remembering one needs 27.
The row on the right counts how many times each subproblem is actually worked out. Without the table it is a spiky mess. With it, every bar is a one. That row is the entire technique in one picture.
When remembering buys nothing
Press factorial-memo. The table is there, the code to use it is there, and it is read 0 times.
Each call asks for something nothing has asked for before, so nothing is ever read back. The calls form a chain rather than a branching tree, and a chain has no overlap to exploit. The memory is not free: it costs space, and here it buys nothing whatsoever.
This is the half that usually goes missing. Recursion plus a table is not dynamic programming. Recursion plus a table plus something actually coming back is.
Top-down and bottom-up are the same table
What you have watched is the top-down form: start from the answer you want, recurse, and write things down on the way back. The bottom-up form fills the same table in order, smallest first, with a loop and no recursion at all.
dp[0] = 0
dp[1] = 1
for (let k = 2; k <= n; k++)
dp[k] = dp[k - 1] + dp[k - 2]Four lines, no tree, no stack frames. The table ends up holding exactly the same numbers in exactly the same slots. Bottom-up is usually a little faster, because there is no call overhead and nothing to run out of, and it is the version you would ship.
Top-down has one real advantage, and it is worth knowing: it only ever computes the subproblems it actually needs. Where a problem has a large table of which any given run touches a small part, bottom-up fills all of it and memoisation fills none of what it does not use.
Finding the subproblem is the hard part
Nothing above is the difficult bit in an exam or an interview. The difficult bit is deciding what the table is indexed by, and there is no way around it being a modelling problem rather than a coding one.
Two questions get you most of the way. What does a partial answer look like, and what is the smallest set of facts that tells you everything you need about one? For the coin problem in the previous lesson, a partial answer is “some amount still owed”, and the amount alone tells you everything. That is why the table has one row per amount and why nothing else needs to be stored.
Once the state is right the recurrence usually writes itself, because it is just “what are my options from here, and what does each cost”. When a problem feels impossible, it is almost always the state that is wrong, not the recurrence.
What it costs
The cost is the number of distinct subproblems multiplied by the work done at each one. Fibonacci has n subproblems and constant work at each, so it is linear. The coin problem has one subproblem per amount and tries every coin at each, so it is the amount multiplied by the number of coins.
That product is also the warning. If your state has three parts, each able to take a thousand values, the table has a billion entries and no amount of cleverness in the recurrence will save you. A problem is tractable by this technique exactly when the number of distinct subproblems is small, which is another way of saying that finding a smaller state is the whole game.
Memory is a real constraint and often a solvable one. Fibonacci only ever looks back two rows, so it can be done in two variables rather than a whole array. Many grid problems only look at the previous row and can be run in a single row. The table you reason with and the table you keep need not be the same size.
Where it turns up
Diff tools and spell checkers compute an edit distance, which is a table of “cheapest way to turn the first i characters into the first j”. Every sequence aligner in biology is the same table. So is the longest-common-subsequence algorithm underneath git diff, the word-wrapping in a typesetter, and the packing decisions inside a scheduler.
The previous lesson ended on a greedy rule that handed over six coins when three would do. The fix is this: instead of taking the best-looking coin and hoping, work out the fewest coins for every amount up to the target, each one built from an answer already worked out. It is slower than greedy and it is never wrong.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
Working out fib(6) without writing anything down takes 25 calls, and one subproblem alone is worked out 8 separate times. What makes it expensive?
With a table, fib(6) takes 11 calls instead of 25, and 4 of those calls are answered from it. What happened to the rest?
Running factorial(6) with a table takes 6 calls and reads the table 0 times. Why does the table earn nothing?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Count the repeats
Working out fib(5) without a table, how many
separate times is fib(2) worked out?Show the answer →Hide the answer
Three.fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). Each fib(3) calls a fib(2) of its own. That is two fib(3)s, each producing a fib(2), plus the one fib(4) asked for directly.
What is the table indexed by?
You are finding the fewest coins that make an
amount, from a fixed set of coins.
What does one entry of the table mean?Show the answer →Hide the answer
dp[a] = the fewest coins that make exactly a.One number in, one number out. Nothing else about the situation matters, which is exactly the test for a well-chosen state: two runs that agree on the amount owed have the same answer ahead of them.
Write the recurrence
Using that table, and coins c in the purse,
write dp[a] in terms of smaller entries.Show the answer →Hide the answer
dp[0] = 0
dp[a] = 1 + min(dp[a - c]) over every coin c ≤ aRead it aloud: to make a, take some coin and then make what is left, as cheaply as possible. The min over coins is the part greedy skipped, because greedy picked one coin instead of considering all of them.
Decide whether a table helps
Merge sort splits an array in half, sorts each
half, and merges. Would memoising the
recursive calls speed it up?Show the answer →Hide the answer
No.Every call is for a different piece of the array, so no result is ever asked for twice. It is the factorial variant again: the structure is a tree, but with no overlap, and a table over a tree with no overlap is storage you pay for and never read.
Shrink the table
A grid problem fills a table of 10,000 rows by
10,000 columns, where each entry depends only
on the one above it and the one to its left.
It will not fit in memory. What now?Show the answer →Hide the answer
Keep one row, not ten thousand.
Each row needs only the row before it, so
overwrite as you go: 10,000 entries instead
of 100 million.You lose the ability to walk backwards through the table and recover the actual path, which many problems need. The usual fix is Hirschberg's trick: solve one half, recurse on the other, and pay a doubling of time to keep the memory linear.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+What is dynamic programming?
Working each subproblem out once and keeping the answer, so that the ones which come back are read rather than recomputed. It needs two things to be worth doing: the best whole answer must be built from best answers to the parts, and those parts must actually be asked for more than once.
+How is it different from divide and conquer?
Only the second condition. Both split a problem into smaller versions of itself. In divide and conquer the pieces are disjoint, so nothing ever repeats and there is nothing to remember. Merge sort never sorts the same piece twice; Fibonacci computes the same number dozens of times.
+Top-down or bottom-up?
Same table, filled in a different order. Bottom-up is a loop, has no call overhead and cannot run out of stack, so it is usually what ships. Top-down only computes the entries a particular run actually needs, which wins when the table is large and mostly untouched.
+How do you find the subproblem?
Ask what a partial answer looks like, and what the smallest set of facts is that says everything about one. That is the state, and it is what the table is indexed by. The recurrence is then just the options available from that state. When a dynamic programming problem feels impossible, the state is usually wrong rather than the recurrence.
+What does it cost?
The number of distinct subproblems multiplied by the work at each one. That product is also the reason a problem can be out of reach: a state with three parts each taking a thousand values is a billion entries, and no recurrence is clever enough to rescue that.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Greedy algorithms, and when they are wrong
The lesson that ends with six coins where three would do. The fix is a table of every amount, each answer built from one already worked out.
Start there →