Tabulation: Filling a Table Instead
The memo from the last tutorial is already a table. It is keyed by subproblem, it holds one answer per key, and by the time the program finishes, every entry that was ever going to be filled has been filled. The only thing the recursion contributed was deciding what order to fill them in.
So skip it. Work the order out yourself, fill the table from one end to the other, and never make a recursive call at all. That is tabulation, and it is what most people have in mind when they say dynamic programming.
A problem worth the trouble
Fibonacci is a poor advertisement for any of this, because nobody has ever urgently needed the fortieth Fibonacci number. Here is the same arithmetic attached to a question somebody might actually ask. A staircase has n steps, you can climb either one step or two at a time, and the task is to count the different ways of reaching the top.
Work backwards from the top step. However you got to step n, your last move was either a small step from n minus 1 or a big one from n minus 2. Those two sets of routes have nothing in common, and between them they cover every route there is, so the count for step n is the count for n minus 1 added to the count for n minus 2.
The base cases deserve a second of thought rather than a guess. There is exactly one way to be standing at the bottom, which is to not have moved yet. There is exactly one way to be on step 1. Those two anchor everything above them.
Below is that table being filled in, one cell at a time, and the arrows are the part to watch: each one points from a cell that is already settled into the cell currently being worked out, which is the recurrence drawn rather than written.
ways(0) = 1 · ways(1) = 1 · ways(i) = ways(i - 1) + ways(i - 2)
across: stair
Each cell needs only the two before it, so the whole table is filled in one left-to-right sweep and never revisited.
Standing at the bottom, there is exactly one way to have got there: do nothing.
Every value gets written exactly once and is never touched again. No stack, no calls, one pass from left to right, and the code is as plain as the picture. The whole function is eight lines.
function climbStairs(n) {
const ways = new Array(n + 1);
ways[0] = 1;
ways[1] = 1;
for (let i = 2; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2];
}
return ways[n];
}Turning any memo into a table
There is a mechanical way across, and it is worth knowing because it means you never have to invent a bottom-up solution from nothing. Write the memoized recursion first, get it correct, and then translate it a piece at a time.
| In the memoized version | Becomes, in the table |
|---|---|
| the memo key | the index into the table |
| each base case | a cell filled in before the loop starts |
| the recursive case | the body of the loop |
| each recursive call | a read of a cell that is already filled |
| the order calls happen to run in | a loop order you pick deliberately |
Only the last row asks anything of you. Everything above it is transcription, and if the recursive version was correct then the transcribed version computes exactly the same numbers, for exactly the same reasons, in a different order, which is exactly why the translation is worth trusting: nothing about the reasoning changed, only the order it runs in.
Two habits make this less error-prone than it sounds. Fill the base cells before the loop rather than special-casing them inside it, so the loop body has one job. And write the loop bounds before the loop body, since the bounds are where the fill order actually lives and it is easier to get them right while the dependency arrows are still fresh in your head.
Fill order is the whole design
The one thing tabulation asks of you that memoization does not is an order. A cell can only be filled once every cell it depends on has been filled already, and working that out is more or less the entire design work in a bottom-up solution. Everything else is transcription.
Climbing stairs makes it look like a non-issue, since every cell reads to its left and left to right is the obvious sweep. Get it wrong on a harder problem and the failure is not subtle. You read a cell that has not been written yet, and depending on the language you get a zero, an undefined, or a crash, none of which points at the real mistake.
A reliable way to check an order is to draw every dependency as an arrow and confirm that none of them point forward. If they all run backwards along the direction you are filling, the order is safe. The grid problems later in this section are that same test applied in two directions at once.
Top-down or bottom-up
| Memoization, top-down | Tabulation, bottom-up | |
|---|---|---|
| Shape of the code | the recursion, plus a store | loops |
| Fill order | works itself out | you have to choose it |
| Subproblems solved | only the ones reached | all of them |
| Stack depth | as deep as the recursion goes | none |
| Easy to shrink the memory | rarely | often |
Memoization is usually quicker to write, because you take a recursion you already believe in and bolt a store onto the side of it, and it has the advantage of skipping subproblems that never come up. Tabulation avoids the stack entirely and opens the door to the memory trick below.
In an interview, write whichever one you can get correct. In production, measure. They compute the same answers, so the choice is about the shape of your code and the shape of the machine rather than about the mathematics.
Throwing most of the table away
Look at the arrows in the widget once more. Each cell reads the two immediately to its left, and nothing ever reaches further back than that. By the time the loop is filling cell 20, cell 3 will never be read again, and it is still sitting there occupying memory for no reason at all. Cell 3 is dead weight.
So stop keeping it. Two variables hold everything the loop needs, and the array disappears.
function climbStairs(n) {
let prev = 1; // ways to reach step i - 2
let curr = 1; // ways to reach step i - 1
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}Memory drops from n cells to a fixed handful, and the running time does not change at all. The trick works whenever a recurrence reaches back only a fixed distance, which covers a surprising share of the problems in this section. Look for it once the algorithm is correct, never before.
It costs you one thing worth naming out loud. With the table gone, there is nothing left to walk back through, so you can report the answer but not the route that produced it. That trade returns in the grid problems, where the filled table is the only record of how the answer was assembled.
Climbing stairs was picked because its recurrence was already familiar from Fibonacci, which let the fill order and the memory trick have the stage to themselves without a second idea competing for attention. The harder skill is different. It is taking a problem you have never seen and working out what the table should hold in the first place.