Memoisation vs Tabulation

A concrete example. Fibonacci

The simplest DP to compare. Same recurrence, f(n) = f(n-1) + f(n-2), written two ways.

# Memoisation
from functools import cache

def fib_memo(n):
    @cache
    def f(k):
        if k < 2: return k
        return f(k - 1) + f(k - 2)
    return f(n)

# Tabulation
def fib_tab(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Tabulation with rolling variables
def fib_rolled(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

All three are O(n) time. The first uses O(n) recursion stack + O(n) cache. The second uses O(n) array. The third uses O(1) extra memory. Tabulation enables the third form; memoisation typically does not.

When memoisation wins

• Sparse state spaces. If only a fraction of states are reachable from the answer's recurrence, memoisation only computes them. Tabulation fills the whole table, including unreachable states.
• Complex state shapes. If the state is a tuple or a structure not easily indexed into an array, hashing is easier than allocating a multi-dimensional table.
• Tree DPs. The recursion mirrors the tree structure naturally. Tabulation requires you to traverse the tree separately and compute values in post-order, twice the code for no gain.
• Quick prototyping. Memoisation lets you write the recurrence directly. Tabulation requires you to plan the order in which states get filled, easy to get wrong on a first pass.

When tabulation wins

• Dense state spaces with all states needed. The cache overhead of memoisation is real; the contiguous array of tabulation is cache-friendly.
• Deep recursion that would overflow the stack. Python's default recursion limit is 1000; on n = 10⁴ a memoised solution crashes while a tabulated one runs fine.
• Space optimisation matters. Rolling rows (O(W) instead of O(n × W) for knapsack, O(1) for Fibonacci) is straightforward in tabulation. Memoisation's cache is harder to slim down because you don't control when entries expire.
• The problem demands iterative implementation. Some interview problems explicitly say "iterative, no recursion." Tabulation satisfies the constraint directly.

Converting between styles

The recipe is straightforward once you've done it a few times.

Memoisation to tabulation

1. List the parameters the recursion uses. The state space is the cartesian product of their ranges.
2. Find the dependency direction. f(i) depends on f(i-1) means we iterate i in increasing order. f(i, j) depends on smaller i and smaller j means we iterate both in increasing order.
3. Replace each recursive call with an array lookup.
4. Handle base cases by initialising the relevant entries of the array.

Tabulation to memoisation

Easier, the recurrence is already explicit. Wrap it in a recursive function with the cache decorator. The base cases become if-statements at the top of the function.

Space optimisation, tabulation's superpower

When the recurrence depends only on the previous row (or the last K rows), the full table is unnecessary. Keep only what you need.

# Knapsack with O(n × W) → O(W) memory
def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):                  # decreasing!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

The decreasing iteration order is what preserves 0/1 semantics, see the knapsack-variants deep-dive. The space saving is from O(n × W) to O(W), for n = W = 10³, that's 10⁶ ints down to 10³.

Gotchas

• Mutating cache keys. If the cached function takes a list or other mutable argument, the cache silently misbehaves. Use tuples or hashable types.
• Closure over mutable state. A memoised function that reads an outer-scope mutable variable can return stale answers when the outer state changes. Pass the state in as a parameter or rebuild the function.
• Tabulation order errors. Iterating in the wrong direction reads uninitialised values (or already-overwritten ones in space-optimised variants). The 0/1 vs unbounded knapsack distinction is a famous instance, same code, one index direction reversed, different problem solved.
• Premature space optimisation. Get the full 2D table working first. Verify correctness. Then roll rows. Premature optimisation produces wrong answers that are hard to debug.
• Returning the wrong cell. The answer is sometimes dp[n], sometimes max(dp), sometimes a reconstructed path. Read the problem statement carefully.

Hybrid approaches

For very large state spaces with sparse reachability (think: graph distance with billions of nodes), neither pure memoisation nor pure tabulation works. Hybrid techniques (bounded memoisation with eviction, beam search, A*) combine the best parts. These are rarely needed in interview problems but are common in production-grade ML and search systems.

Picking for an interview

Default to memoisation. Read off the recurrence; wrap in a decorator; check correctness. If the interviewer says "now make it iterative" or "now optimise space", convert to tabulation. If neither comes up, you're done. The recursive form is what they actually wanted you to derive; the iterative form is implementation polish.

What to read next

The State Design Templates piece covers the six DP shapes that drive when each style shines. The Knapsack Variants deep-dive shows the iteration-direction trick in detail. The Dynamic Programming module ties everything together.