Memoization and Tabulation

The last tutorial finished on a count: twenty-five calls to answer seven questions. Put that way, the fix more or less announces itself. Answer each question once, write the answer down somewhere, and look it up the next time somebody asks for it.

That's memoization, and in most languages it costs about three lines of change to a function you've already written. The function keeps its shape. It keeps its base case, it keeps its recursive case, and the induction argument from the recursion guide goes through completely unchanged, which matters more than it might look: you're not being asked to trust a new algorithm, only a store sitting beside an old one.

Filling those same answers in from the bottom up, with no recursion at all, is tabulation. Both are on this page, because the second is easiest to understand as a rewrite of the first, and because the choice between them comes up every single time you solve one of these problems.

Memoization in three lines

function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);          // already answered
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);                           // write it down
  return value;
}

Two of those lines carry the whole idea. One checks the store before doing any work at all, one writes the result into the store on the way back out. The arithmetic in between is the original recursion, untouched.

The Python version takes a small detour worth flagging, since it catches people. Writing memo equals empty dictionary directly in the parameter list would build that dictionary once, at the moment the function is defined, and then every later call anywhere in the program would quietly share it. The None check builds a fresh one per top-level call.

Turn the memo on in the widget below and watch what it does to the same fib(6) tree.

Twenty-five calls become eleven. The repeated subtrees don't shrink, they stop existing altogether, since a call that finds its answer waiting in the memo returns on the spot and never grows anything beneath it. What's left is the seven distinct questions plus four lookups, drawn dashed so you can tell at a glance which calls did work and which just collected it.

What memoization costs now

There's a formula for the cost of a memoized recursion, and it's friendlier than most complexity arguments. Count the distinct subproblems. Count the work each one does on its own, not counting its recursive calls. Multiply the two.

Fibonacci has n plus 1 distinct subproblems and each does a single addition, so the whole thing runs in linear time. That's down from exponential, and the price is a table holding n entries. Trading memory for time is the standard bargain of this entire section, and it's very nearly always worth taking.

Choosing the key

The one real decision in memoization is what to use as the key, and getting it wrong produces the most confusing class of bug in the topic. The rule fits in a sentence: the key has to capture everything the answer depends on, and nothing else.

Put too little in the key and the store hands back an answer that was computed under different circumstances, which shows up as the algorithm being subtly and inconsistently wrong. Put too much in and no two calls ever match, so the store fills up, never hits, and the only thing you've bought is memory pressure.

Fibonacci makes this look trivial, since there's one argument and it's obviously the key. Binomial coefficients are the honest version. C(n,k) counts the ways of choosing k things out of n, and it obeys a rule with the same shape as Fibonacci's.

C(n, 0) = 1
C(n, n) = 1
C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

The reasoning behind that middle line is worth a moment. Fix your attention on the first item. Every group of k either contains it or doesn't, those two cases can't both happen and between them they cover everything, so counting each and adding gives the total. Two arguments change on the way down, which means the key has to be the pair. Store on n alone and C(6,3) will cheerfully hand back whatever C(6,1) worked out earlier.

The widget below opens on Choose with the memo already switched on, so the entries in the memo panel are written as pairs rather than single numbers. That small change in what a key looks like is what pushes the two-dimensional problems later in this section toward a grid.

What memoization does not fix

Two things, and neither is obscure. The first is the call stack. A memoized recursion still recurses, so a problem needing a hundred thousand levels of depth runs out of stack long before it runs out of ideas, and plenty of languages have no tail-call elimination to fall back on. Python stops at a thousand frames by default.

The second is that the cost formula cuts both ways. Distinct subproblems multiplied by work per subproblem is an honest number, and when the first factor's already astronomical, storing results does nothing for you. A memo turns repeated work into stored work. It can't turn an exponential number of genuinely different questions into a small one.

The version you will actually write

Most languages ship something that does all of this for you. Python keeps a decorator in the standard library: put a cache above the function and every call gets stored, keyed on whatever arguments it was handed. The body stays exactly as it was in the naive version, which is the whole appeal.

from functools import cache


@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

It's worth knowing and worth handling with some care. The decorator keys on the arguments, so every argument has to be hashable, and passing a list in fails on the spot. It also holds entries forever unless you switch to the version that takes a size limit, which is harmless inside a script that runs once and a slow leak inside a service that runs for months.

There's a reason to write the store out by hand at least once before reaching for the decorator. The decorator quietly answers the question you're supposed to be thinking about. What identifies a subproblem is the decision this entire topic turns on, and a tool that settles it for you by taking the whole argument list is right most of the time and silently wrong the rest of it.

Only the subproblems that come up

Memoization does one thing that's genuinely awkward to reproduce any other way. It solves only the subproblems that actually arise, because the recursion asks for what it needs and never goes looking for anything else, so a problem with an enormous space of possible subproblems and a narrow path through it pays only for the path.

Fibonacci hides this, since reaching fib(40) means passing through every smaller value along the way and there's nothing to skip. Plenty of problems aren't built like that. Hold on to the point, because tabulation, in the second half of this page, trades this property away for something else worth having.

Both of those limits point the same direction. If the recursion exists only to decide which subproblem gets solved first, and every subproblem's going to be solved sooner or later anyway, then the recursion can be thrown away and the answers filled in directly.

Tabulation: the same table without the recursion

The memo from the first half of this page is already a table. It's 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's tabulation, and it's what most people picture when they say dynamic programming.

Climbing stairs, bottom-up

Fibonacci is a poor advertisement for any of this, because nobody's ever urgently needed the fortieth Fibonacci number. Here's 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's exactly one way to be standing at the bottom, which is to not have moved yet. There's 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's already settled into the cell currently being worked out, which is the recurrence drawn rather than written.

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's a mechanical way across, and it's worth knowing because it means you never have to invent a bottom-up solution from nothing. Write the memoized recursion first, get it correct, then translate it a piece at a time.

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. That's 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's 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 doesn't 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 isn't subtle. You read a cell that hasn't 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 none of them point forward. If they all run backwards along the direction you're 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 is usually quicker to write, since 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's 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 doesn't 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's correct, never before.

It costs you one thing worth naming out loud. With the table gone, there's 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's taking a problem you've never seen and working out what the table should hold in the first place.