Memoization and Tabulation

Memoization Overview

function fib(n, memo = new Map()) {
  if (n <= 1)
    return n;

  if (memo.has(n)) 
    return memo.get(n); // use already calculated value

  const value = fib(n - 1, memo) + fib(n - 2, memo);

  memo.set(n, value); // store value just calculated

  return value;
}

The only two lines added here to implement memoization are the ones with comments. One line checks the store before doing any work at all, the other writes the result into the store on the way back out.

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

25 to 11 calls seems like a small improvement, but this increased efficiently gets more significant as the number increases. 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.

Memoization Cost

Fibonacci has 2ⁿ total function calls n + 1 distinct calculations and each does a single addition, so with memoization it runs in O(N), and without it runs in O(2ⁿ) time complexity.

Choosing the key

The one real decision in memoization is what to use as the key, which must be unique! Almost all of the time, the key is the inputs to a function. For example the key for the value of F(1, 2) would probably be a tuple like (1, 2) in python. What the key looks like depends on the programming language, most languages would use some kind of list type like tuples in python, but some programming languages have their own required rules. In JavaScript, object keys are strings and you may opt for a key that looks like `1-2` or the general form`${a}-${b}` .

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

This case is just like the one we explored earlier, and the key in code would be something like (n, k).

What memoization does not fix

• 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.
• 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.

In Practice

Most languages ship something that does all of this for you, since the store track lines of code causes clutter. 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, usually harmless inside a script that runs once, but it can be 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, but it fails quietly.

Tabulation: no recursion!

Memoization uses recursion to recursively find the next answer from previous answers, and the memoization part caches values that were already computed. You may have realized that in this case, the recursion part is actually pretty much optional for lots of problems like Fibonacci. Rather than using a recursive call to produce n numbers, we can simply loop in the range [0, n], and then use the sum of the two previous rows to get the current. This technique is tabulation!

Climbing stairs

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.

This problem can be solved using recursion, so lets work backwards starting at the step n. 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 ways(n) = ways(n - 1) + ways(n - 2) . In other words, we have the nth Fibonacci number of ways to reach the nth step.

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];
}

Wait a minute! A complete tabulation here isn't even necessary. We can simplify the code further, by only storing two values instead of an array.

function climbStairs(n) {
  let ahead = 1
  let behind = 1
  for (let i = 2; i <= n; i++) {
    let sum = ahead + behind
    behind = ahead
    ahead = sum
  }
  return ahead;
}

Turning any memo into a table

Let's figure out how to translate a memo-style algorithm into the tabular one.

Everything except for the last row is trivial to do. 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.

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 hard part.

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 you'll start accessing calculated values that don't exist yet. In other words, the most important part about using the tabulation method is getting the order correct!

A reliable way to check an order is to visualize 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

In an interview, write whichever one you can get correct, usually some problems tend to one over the other.

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.