Memoization vs Tabulation

Naive recursive Fibonacci recomputes fib(5) inside fib(6), inside fib(7), and so on — the same subproblem gets solved exponentially many times, turning an $O(n)$ problem into $O(2^n)$ work. Dynamic programming fixes this by never solving the same subproblem twice, and there are exactly two ways to enforce that: cache results as you naturally recurse (memoization), or compute results in a deliberate order so every dependency is already known when you need it (tabulation).

The idea: same subproblems, opposite direction

Memoization (top-down) keeps the natural recursive structure of the problem, but wraps it in a cache: before computing f(n), check if it's already in a dictionary; if so return it, otherwise compute it, store it, and return. It only ever computes subproblems that are actually reachable from the original call — if some large chunk of the subproblem space is never needed for this particular input, memoization never touches it.

Tabulation (bottom-up) throws away recursion entirely. You identify the order subproblems must be solved in (smallest first, usually), allocate an array or table, and fill it in a loop, so that by the time you need table[i], table[i-1] and whatever else it depends on are already sitting there computed. It avoids Python's or C++'s function-call overhead and any risk of stack overflow on deep recursion, and it makes memory optimization obvious — if table[i] only ever depends on table[i-1], you don't need the whole array, just the last one or two values.

Both give the same asymptotic complexity for problems where every subproblem is eventually needed anyway — $O(n)$ time and space for Fibonacci, for instance — but tabulation is usually faster in practice by a constant factor, and memoization is usually faster to write correctly, because it mirrors the recursive definition you already have in your head.

Worked example: Fibonacci both ways

fib(5) top-down calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2). Without caching, fib(3) is computed twice here (and far more at larger $n$). With a cache dictionary, the second call to fib(3) returns instantly. Bottom-up instead builds table = [0, 1] then loops $i$ from 2 to 5, setting table[i] = table[i-1] + table[i-2] each time — table becomes [0,1,1,2,3,5], computed once, no recursion at all.

# memoization
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)

# tabulation
def fib_tab(n):
    prev, curr = 0, 1
    for _ in range(n):
        prev, curr = curr, prev + curr
    return prev

Where it shows up

Almost every dynamic programming interview question can be written either way, and interviewers sometimes explicitly ask for the "iterative bottom-up version" after a recursive solution to test whether you actually understand the dependency structure, not just the recursion. On a desk, both patterns appear in backtest engines: memoized recursive signal calculations avoid recomputing shared sub-signals across strategies, while tabulated rolling-window statistics (moving averages, cumulative P&L) are computed once, left to right, over the full price history.