Memoization versus Tabulation

A dynamic programming problem defines subproblems and a recurrence: a rule expressing each subproblem's answer in terms of the answers to smaller subproblems. Picture every subproblem as a node in a directed acyclic graph, with an edge from subproblem $B$ to subproblem $A$ whenever $A$'s recurrence directly needs $B$'s answer. Because the graph is acyclic (no subproblem transitively depends on itself), any topological order of this DAG is a legal evaluation order.

Memoization (top-down) starts at the original query and recurses exactly as a naive divide-and-conquer algorithm would, but wraps every call in a check: "have I already computed this subproblem?" If yes, return the cached value instantly; if no, compute it recursively, store it, and return it. The recursion itself discovers which subproblems are needed and in what order, following the DAG backward from the query node via a depth-first traversal, computing children before parents implicitly through the call stack.

Tabulation (bottom-up) inverts the perspective. Before writing any solving code, you fix an explicit iteration order over subproblem indices — typically increasing size, increasing index, or some other order provably consistent with the DAG's edges — and then fill an array or table cell by cell, using only already-filled entries. There is no recursion; the "recursion" has been replaced by a loop nest whose loop bounds guarantee every dependency is ready before it's read. Both approaches are instances of the same idea: decompose, cache, reuse — the term dynamic programming in Introduction to Dynamic Programming refers to this caching discipline over a subproblem DAG, not to anything "dynamic" in the everyday sense.

Memoization, mechanically

Start from the top-level call. At each call: 1. Compute a canonical key identifying the subproblem's parameters. 2. Look the key up in a cache (a hash map or an array indexed by the key). 3. If present, return the cached value — no further recursion. 4. If absent, recursively evaluate the subproblem's dependencies (each of which repeats this same procedure), combine them via the recurrence, store the result under the key, and return it. ``` memo <- empty map function SOLVE(state): if state is a base case: return BASE_VALUE(state) if state in memo: return memo[state] // Recurrence: combine solutions to smaller subproblems result <- COMBINE( SOLVE(child_1(state)), SOLVE(child_2(state)), ... ) memo[state] <- result return result // Entry point return SOLVE(initial_state) ``` Fibonacci is the smallest faithful instance: ``` memo <- empty map function FIB(n): if n <= 1: return n if n in memo: return memo[n] result <- FIB(n - 1) + FIB(n - 2) memo[n] <- result return result ```

Tabulation, mechanically

Fix the domain of subproblems (say, all integers from `0` to `n`, or all pairs `(i, j)` with `0 ≤ i ≤ m, 0 ≤ j ≤ n`). Prove — usually by inspection of the recurrence — that filling entries in increasing order of some index respects dependencies. Then loop: ``` table <- array indexed over all subproblem states initialize base cases directly in table for state in TOPOLOGICAL_ORDER(all non-base states): table[state] <- COMBINE( table[child_1(state)], table[child_2(state)], ... ) return table[initial_state] ``` Fibonacci, tabulated: ``` function FIB(n): if n <= 1: return n table[0] <- 0 table[1] <- 1 for i from 2 to n: table[i] <- table[i - 1] + table[i - 2] return table[n] ``` Note the loop order `i from 2 to n` is exactly a topological order of the dependency DAG, since `table[i]` only ever reads `table[i-1]` and `table[i-2]`, both already filled.

The DAG view, illustrated

The figure below shows the subproblem DAG for `FIB(5)`. Memoization discovers this graph by depth-first recursion from the top (dashed arrows show the first time each node is visited); tabulation fills it left-to-right by index, which is simply a different — and here, simpler — traversal of the same graph.

Every edge points from a smaller subproblem to the larger one that consumes it. A topological order of this DAG is any order that lists each node after all nodes that point into it — tabulation's `i` from `0` to `n` is one valid such order; memoization's recursive descent-then-return is another, discovered dynamically and driven by the call stack rather than fixed in advance.

Correctness (both methods). The proof rests on strong induction over the subproblem DAG's topological levels. Claim: every value written into `memo[state]` or `table[state]` equals the true value of that subproblem, defined by the given recurrence and base cases.

• Base case: base states are assigned their defining value directly (not through the recurrence), and this is correct by definition.
• Inductive step: consider a non-base state $s$ whose dependencies are $c_1, \dots, c_k$. By the DAG's acyclicity, each $c_i$ is strictly "smaller" in the topological order than $s$. Inductively, by the time $s$ is computed — either because tabulation's loop has already passed index $c_i$, or because memoization's recursion into $c_i$ has already returned and cached a value — each `table[c_i]` / `memo[c_i]` already holds the correct value. Since $s$'s value is computed by applying `COMBINE` to exactly these correct values, it is correct too.
• By induction over all states in topological order, every state (in particular the initial query) is computed correctly.

The only extra step memoization needs is the observation that a cache lookup never recomputes: the first time a state is visited it computes and stores the true value, and every subsequent visit — regardless of which branch of recursion triggers it — reads that same stored true value. This guarantees the "compute once" property that both strategies share.

Time complexity. Let $P$ be the number of distinct subproblems ever needed and let $W$ be the worst-case work to combine a subproblem's dependencies (excluding recursive calls). Then:

for both memoization and tabulation, provided they end up visiting the same set of subproblems. This is the "compute once" guarantee: without caching, a naive recursion can retrace exponentially many redundant paths through the DAG (e.g., naive Fibonacci is $\Theta(\phi^n)$); with caching, each of the $P$ distinct nodes is charged $O(W)$ exactly once, plus $O(1)$ or $O(\log P)$ per cache hit depending on whether the cache is an array or hash map. There is a subtlety worth being honest about: memoization visits only the subproblems reachable from the initial query, while tabulation (as usually written) fills the entire declared table, including cells that might never be needed by the top-level answer. If the reachable set is a small fraction of the full table's domain — a common situation with sparse or input-dependent recursions, such as edit-distance variants with early stopping, or interval DP where far-apart intervals never arise — memoization can be asymptotically faster in practice, even though both are "polynomial in the table size" in the worst case. Tabulation can be restricted to a smaller domain too, but doing so requires the programmer to precompute the reachable set, which is exactly the extra bookkeeping memoization gets automatically from the recursion.

Space complexity. Both need $\Theta(P)$ space for the cache/table in the worst case, where $P$ is the number of distinct subproblems. Tabulation has an added advantage: because the fill order is known in advance, you can often discard old rows once they are no longer needed, collapsing an $O(nm)$ table (as in Longest Common Subsequence or Edit Distance) to $O(m)$ or $O(1)$ extra rows via a rolling array. Memoization's cache, by contrast, generally must retain every entry, since future recursive calls in arbitrary order might request any previously computed subproblem — you cannot safely predict which cached entries are "done being needed." Memoization also carries an implicit cost tabulation does not: call-stack depth. Deep recursion (e.g., a chain of $n$ dependent calls) can overflow the call stack in languages with limited stack size, whereas tabulation's iterative loop uses $O(1)$ stack frames regardless of $n$. This is a genuine correctness risk in practice, not just a performance nuance.

Constant-factor overhead. Recursive calls carry function-call overhead (stack frame setup, argument passing, possibly hashing a composite key for the cache). Tabulation's iterative array accesses are typically faster in wall-clock time for the same asymptotic complexity, because array indexing beats hash-map lookups and loop iteration beats function calls on most hardware.

Consider the classic 0/1 knapsack recurrence, which will be treated fully in The 0/1 Knapsack Problem. Let `V(i, w)` be the best value achievable using items `1..i` with capacity `w`:

Take 3 items with (weight, value) pairs `(2,3), (3,4), (4,5)` and capacity `W = 5`.

Tabulation builds the full table for `i = 0..3`, `w = 0..5`:

Every one of the 24 cells is computed, in row-major order, because each cell `(i, w)` only needs row `i-1`, already filled. The final answer `V(3, 5) = 7` (items 1 and 2, total weight 5, value 7).

Memoization, called as `SOLVE(3, 5)`, only computes the cells actually reachable by recursive need: ``` SOLVE(3,5) needs SOLVE(2,5) and SOLVE(2,1) SOLVE(2,5) needs SOLVE(1,5) and SOLVE(1,2) SOLVE(2,1) needs SOLVE(1,1) [weight 3 > 1, so only one branch] SOLVE(1,5) needs SOLVE(0,5) and SOLVE(0,3) SOLVE(1,2) needs SOLVE(0,2) and SOLVE(0,0) SOLVE(1,1) needs SOLVE(0,1) [weight 2 > 1, so only one branch] ``` Here the reachable set is `{(3,5), (2,5), (2,1), (1,5), (1,2), (1,1), (0,5), (0,3), (0,2), (0,0), (0,1)}` — 11 cells, versus 24 for full tabulation. Both return the correct answer `7`, but memoization skipped 13 cells that tabulation computed unnecessarily (e.g., `(2,3)`, `(2,4)`, `(1,3)`, `(1,4)` are never on any path to the final query). This concretely demonstrates the "reachability gap" discussed above: for this small capacity-restricted instance, memoization does noticeably less work, even though both are $O(nW)$ in the worst case over all inputs.

The subproblem-caching idea underlying both memoization and tabulation traces to the founding of dynamic programming as a field. Richard Bellman formalized the "principle of optimality" and the general recurrence-based decomposition of multistage decision problems in the 1950s, giving the mathematical backbone that both top-down and bottom-up implementations later exploited. The word "memoization" itself was coined somewhat later, in the context of functional programming and caching function results, but the underlying mathematics is Bellman's.

Compilers and interpreters memoize type-checking and constant-folding results across repeated subexpressions to avoid recomputation during a single compilation pass. Spreadsheet engines like Excel and Google Sheets essentially tabulate: they compute a topological order over cell dependencies and re-evaluate formulas bottom-up whenever inputs change, while incremental recalculation engines add a memoization-like cache to avoid recomputing unaffected cells. Bioinformatics pipelines use tabulated dynamic programming at scale for sequence alignment — the same recurrence family as Edit Distance and Longest Common Subsequence — because genome-scale tables benefit enormously from the rolling-array space reduction that tabulation enables, shrinking memory from gigabytes to megabytes. Route-planning and logistics systems (ride-sharing dispatch, network routing protocols) often use memoized recursive search instead, since only a small, input-dependent slice of the full state space is ever explored per query, and precomputing the entire table would be wasteful. Functional programming languages and modern web frameworks (React's `useMemo`, Python's `functools.lru_cache`) expose memoization directly as a language or library primitive, making the top-down caching pattern a one-line annotation rather than hand-written bookkeeping.

Ask the tutor: How do memoization and tabulation each play out concretely in the 0/1 knapsack recurrence's table versus recursion tree?