Memoization vs Tabulation

Memoization is top down. You write the recursive solution you already have and add a cache so that each subproblem is computed once and reused. Tabulation is bottom up. You identify the states, write them out in an order where every dependency has already been computed, and fill the table iteratively.

They produce the same answers, and the choice between them is mostly about engineering rather than algorithms.

Memoization has two practical advantages. The code looks like the recursive solution you would write anyway, which makes it easier to derive and to check. And it only computes the states that are actually reachable, so if the input makes most of the state space irrelevant you do not pay for it.

Tabulation has two practical advantages. It uses a predictable, bounded amount of memory, usually a single flat list rather than a dictionary plus a recursion stack. And it has no recursion depth limit, so it will not blow the stack on an input where the recursion is deep, which is the classic reason a memoised Fibonacci fails on a large index even though the answer is trivial to compute bottom up.

The trade-off to name in an interview is that these are not mutually exclusive and the choice follows from the problem. If the state space is huge but only a slice is reachable, memoize. If the recursion depth could be large or you want predictable memory, tabulate. A hybrid is also common: memoize during development for clarity, then rewrite bottom up once the answer is right, because the bottom-up version is often several times faster in practice even when the asymptotics match.

Climbing a staircase of n steps taking one or two steps at a time. The memoized version recurses and caches; the tabulated version fills a table from the bottom up.

def climb_memo(n, memo):
    if n <= 2:
        return n
    if n not in memo:
        memo[n] = climb_memo(n - 1, memo) + climb_memo(n - 2, memo)
    return memo[n]


def climb_table(n):
    table = [0] * (n + 1)
    table[0], table[1] = 1, 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(climb_memo(10, {}), climb_table(10))

The outputs are 89 and 89, so the two approaches agree. There are 89 distinct ways to climb ten steps when each move is one or two steps, which is the eleventh Fibonacci number.

The mechanism is the same recurrence in both cases. The number of ways to reach step i is the number of ways to reach step i minus one plus the number of ways to reach step i minus two, because the last move is either one step or two steps. The memoized version evaluates that recurrence on demand and stores each answer in a dictionary keyed by the step. The tabulated version evaluates the same recurrence in a loop, reading two entries that were written on the previous iterations.

The trade-off to name is that the memoized version needs a dictionary, a recursive call per state and a stack that can grow as deep as n, while the tabulated version needs a single list of n plus one entries and no stack at all. For large n the tabulated version is faster in wall-clock terms and cannot overflow the stack. The memoized version's advantage is that it computes only reachable states, which matters when the state space is a grid or a graph and most of it is off the route.