Memoization vs Tabulation

Dynamic Programming (DP) solves a problem by breaking it into overlapping subproblems and storing each subproblem’s answer so it is computed at most once. There are two flavors of doing this: memoization (top-down — write the recursion, cache the results) and tabulation (bottom-up — fill an explicit table in a loop). They compute the same answer with the same asymptotic complexity, but differ in constants, ergonomics, space optimizability, and which subproblems they actually visit. This note is the foundational primer that every other DP note in this vault links back to.

1. Intuition — The Lazy Student vs the Methodical Student

Two students need to solve the same homework: compute the 30th Fibonacci number, where fib(n) = fib(n-1) + fib(n-2) and fib(0) = 0, fib(1) = 1.

Student A (memoization, “top-down”) picks up a pen and asks: “What does the problem ask? fib(30). To answer it I need fib(29) and fib(28). To get those I need their two predecessors, and so on.” She keeps a notebook open. Whenever she finishes a subproblem (say fib(15) = 610), she writes the result in the notebook. Whenever a recursive call asks for a value she already wrote down, she just reads it back instead of recomputing. The recursion tree she would have explored is huge (it has roughly 2^30 leaves if no caching is done — see Big-O Notation), but the notebook collapses it down to 31 distinct subproblems.

Student B (tabulation, “bottom-up”) doesn’t recurse at all. He builds a table dp[0..30], fills dp[0] = 0, dp[1] = 1, then loops i = 2..30 writing dp[i] = dp[i-1] + dp[i-2]. He never asks a question larger than what he has already answered. When the loop finishes, dp[30] contains the answer.

Both students do exactly 31 additions. Student A’s recursion + notebook = memoization. Student B’s loop + table = tabulation. They are two ways of materializing the same set of subproblem answers; the question is whether you discover the dependency graph on demand (memoization, lazy) or traverse it in topological order from the bottom (tabulation, eager).

Richard Bellman coined “dynamic programming” in the 1950s while working at RAND on multistage decision processes (Bellman 1957, Dynamic Programming). The famously cryptic name was chosen partly to disguise mathematical research from a defense-budget reviewer who disliked the word “research” — Bellman wanted something “impossible to use pejoratively.” The technical core is older: it is just the principle that an optimal solution composes from optimal solutions to its subproblems (the principle of optimality), encoded as a recurrence on a state space.

2. When Is a Problem a DP Problem? — The Recognition Checklist

Recognizing a DP problem from a problem statement is the single hardest skill in interview prep. The two necessary conditions are:

1. Overlapping subproblems. A naive recursion would compute the same subproblem many times. Fibonacci’s naive recursion calls fib(28) once for fib(30) and once for fib(29) — they overlap. By contrast, Merge Sort’s recursion splits the input into disjoint halves; nothing overlaps, so caching gains nothing — that’s pure divide-and-conquer, not DP.
2. Optimal substructure. The optimal answer to the whole problem can be expressed in terms of optimal answers to subproblems. Shortest path in a graph has optimal substructure: a shortest A→C path that goes through B contains a shortest A→B path as a prefix. Longest simple path does not have optimal substructure — a longest A→C path may not contain a longest A→B path as a prefix because the longest A→B path might use up vertices we needed for B→C.

Practical recognition signals from a problem statement:

• The objective has the words maximum, minimum, count the number of ways, is it possible to, or longest / shortest — these are 90% of DP problems.
• The input is a sequence (string, array) or a grid, and at each position you make a small discrete choice (take/skip, left/right/down, match/mismatch, cut/don’t cut).
• A naive brute-force solution would explore an exponential tree of choices (2^n, n!, Catalan number), but many of those branches re-encounter the same intermediate state.
• A state can be described by a small tuple of integers — typically 1 to 4 dimensions — and the answer for one state depends on a constant number of “smaller” states.

If those signals are present, sketch the recurrence first; pick top-down vs bottom-up second.

3. The DP Recipe — Five Steps That Apply Every Time

Every DP solution in this vault (and basically in the interview literature) follows the same five-step construction:

1. Define the state. Decide what tuple (i, j, k, ...) indexes a subproblem. The state must be small enough that the total number of states is polynomial. For 01 Knapsack, the state is (i, w) = “first i items considered, capacity w remaining.” For Longest Common Subsequence, it is (i, j) = “prefix of length i of string A vs prefix of length j of string B.”
2. Write the recurrence. Express dp[state] in terms of dp[smaller_state_1], dp[smaller_state_2], .... This is the creative step. Usually it is a min, max, or sum over a small set of choices (“take this item or skip it”).
3. Identify the base cases. What is dp at the smallest possible states? Empty input, length 0, capacity 0. Get these wrong and the entire table is wrong.
4. Choose an order of evaluation. For tabulation, you must fill dp in an order such that whenever you compute dp[state], all states it depends on are already computed. This is a topological order on the subproblem dependency DAG (Directed Acyclic Graph). For memoization, the recursion handles ordering automatically.
5. Reconstruct (if needed). dp[final_state] gives the value of the optimal answer. To recover the actual solution (the chosen items, the LCS string, the path), either store back-pointers during step 4 or trace the recurrence backward from the final state.

The recipe is mechanical once you internalize it. The hard part is step 1–2; the rest is bookkeeping.

4. Tiny Worked Example — Fibonacci, Both Ways

We use Fibonacci because it is the smallest possible DP. The recurrence is fib(n) = fib(n-1) + fib(n-2) with fib(0) = 0, fib(1) = 1.

State: n. Recurrence: as above. Base: fib(0)=0, fib(1)=1. Order (bottom-up): n = 2, 3, ..., target.

The naive recursion (no caching) has running time T(n) = T(n-1) + T(n-2) + O(1), which is itself a Fibonacci-shaped recurrence and grows as O(φ^n) where φ ≈ 1.618 is the golden ratio — exponential. With caching, every distinct subproblem fib(0), fib(1), ..., fib(n) is computed exactly once: O(n) time, O(n) space.

Memoization snapshot for fib(5) — the order in which subproblems are first computed (depth-first from the top):

Call order	Subproblem	Value
1	fib(5) enters, recurses on fib(4) first	(pending)
2	fib(4) enters, recurses on fib(3)	(pending)
3	fib(3) enters, recurses on fib(2)	(pending)
4	fib(2) enters, recurses on fib(1)	(pending)
5	fib(1) returns base case	1
6	fib(2) recurses on fib(0), returns base	0
7	fib(2) returns 1+0 and caches	1
8	fib(3) recurses on fib(1) — cache hit	1
9	fib(3) returns 1+1, caches	2
10	fib(4) recurses on fib(2) — cache hit	1
11	fib(4) returns 2+1, caches	3
12	fib(5) recurses on fib(3) — cache hit	2
13	fib(5) returns 3+2, caches	5

Tabulation snapshot for fib(5):

Step	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
init	0	1	—	—	—	—
i=2	0	1	1	—	—	—
i=3	0	1	1	2	—	—
i=4	0	1	1	2	3	—
i=5	0	1	1	2	3	5

Same six values, computed in the same number of additions. Different order, different mechanism.

5. Pseudocode

Memoization (top-down):

memo := empty map
function f(state):
    if state in memo:
        return memo[state]
    if state is a base case:
        result := base_value(state)
    else:
        result := combine(f(smaller_1), f(smaller_2), ...)
    memo[state] := result
    return result
answer := f(initial_state)

Tabulation (bottom-up):

dp := table indexed by state
fill dp[base_states] with base_values
for state in topological_order(dependency_DAG):
    dp[state] := combine(dp[smaller_1], dp[smaller_2], ...)
return dp[final_state]

Both produce the same answer when set up correctly. The differences are operational — see §8.

6. Python Implementation — Both Flavors

Memoization with functools.lru_cache:

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The @lru_cache(maxsize=None) decorator transparently memoizes. Behind the scenes Python wraps fib in a function that consults a hash map keyed by the argument tuple before invoking the body. lru_cache is the standard idiom; functools.cache (Python 3.9+) is a thinner equivalent without the LRU eviction (which we never want for a DP cache anyway because we want all entries to stick around).

Tabulation:

def fib_table(n: int) -> int:
    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-array space optimization (because dp[i] only depends on the two previous entries, we keep only those):

def fib_rolling(n: int) -> int:
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

This is O(n) time and O(1) space. The technique — collapsing the table to just the entries the recurrence actually reads — is the rolling array optimization and applies whenever the recurrence has a bounded look-back depth (here, depth 2). 01 Knapsack uses the same trick to collapse a 2D dp[i][w] to a 1D dp[w].

7. Complexity — Counting States and Transitions

The general DP complexity formula:

total time  = (number of distinct states) × (work per state)
total space = (number of states stored)   × (size of each entry)

The “work per state” is the cost of evaluating the recurrence for one state — usually O(1) if the recurrence has a constant number of terms, or O(k) if it sums/maxes over k choices.

For Fibonacci: n states, O(1) work each → O(n) time, O(n) space (or O(1) with rolling array).

For 01 Knapsack: n × W states, O(1) work each → O(nW) time, O(nW) space (or O(W) with rolling).

For Longest Common Subsequence: m × n states, O(1) work each → O(mn) time and space.

For matrix-chain multiplication (a classic 2D DP from CLRS Ch. 15.2): n² states, O(n) work each (try every split point) → O(n³) time.

Recognizing this product structure makes complexity analysis automatic.

8. Memoization vs Tabulation — When Each Wins

Both are correct DP. Choose based on these trade-offs.

8.1 Memoization wins when

• The recurrence is naturally recursive and the topological order is non-obvious. Tree DP, interval DP, and game-theory DP (minimax with memo) often have awkward iteration orders; the recursion handles it for free.
• You don’t visit every state. If the answer to f(initial_state) only requires a small fraction of the full state space, memoization computes only the reachable states. Tabulation computes them all. Example: a knapsack with very specific constraints might only need 1% of the n × W cells.
• Code clarity matters. Recursion + cache reads almost identically to the math recurrence, which is good for first drafts and for explaining the algorithm in interviews.

8.2 Tabulation wins when

• You need every state anyway. Most “fill the table” DPs visit every cell, so the laziness of memoization is wasted overhead.
• You want to apply space optimization. Rolling-array tricks (collapse O(nW) to O(W)) are natural in tabulation and awkward in memoization (because the recursion expects the full cache). Whenever the recurrence has bounded look-back depth k along one dimension, tabulation lets you keep only k rows or columns.
• Stack depth would explode. Memoizing recursion is still recursion; for n = 10^5, you blow Python’s default 1000-frame stack. Either rewrite as tabulation or call sys.setrecursionlimit. Tabulation is loop-based and never has this problem.
• Constant-factor speed matters. A loop in tabulation has tighter constants than a recursive call (no frame setup, no hash lookup, better cache locality). For tight inner loops on large inputs, tabulation can be 3-10× faster wall-clock at the same O(...).
• You need to reconstruct the path. Backtracking through a populated table is straightforward; backtracking through a memoization cache requires the same machinery.

In practice: write the memoization first (it mirrors the recurrence and is easier to get right), then translate to tabulation if you need the speed or space optimization. Many interview answers are accepted in either form.

9. Converting Between Memoization and Tabulation

The conversion is mechanical once you have a memoized solution:

1. Identify the state space — the set of arguments you memoize on.
2. Allocate a table the size of the state space.
3. Fill base cases.
4. Determine the topological order of the subproblem dependency DAG. For most DPs this is just “increasing i, then increasing j” or similar; for tree DPs it is “post-order traversal of the tree.”
5. Replace each recursive call f(smaller) in the recurrence with a table read dp[smaller].

The reverse direction (tabulation → memoization) is also mechanical: write a recursive function whose body matches the table-fill logic and decorate with lru_cache.

The hardest part is step 4 — the topological order. For 01 Knapsack with rolling-array, this requires iterating capacity in reverse, which is a famous pitfall — see that note’s pitfall section.

10. The State-Graph View

A useful mental model: every DP defines a directed acyclic graph whose nodes are subproblem states and whose edges are dependencies (a → b means “computing dp[a] needs dp[b]”). The recurrence is the edge weight or aggregation rule.

• Memoization is a depth-first traversal of this DAG starting from the goal state, with caching to avoid revisiting nodes.
• Tabulation is a topological-order traversal, computing every node in a forward sweep.
• Bellman-Ford is exactly this view applied to a literal graph: the state is (vertex, ≤k edges), and the recurrence is shortest-path relaxation. Bellman-Ford’s V-1 outer iterations correspond to filling 1-edge, 2-edge, …, (V-1)-edge layers of the DP table.

This view also clarifies why DP requires acyclic subproblem dependencies. If dp[a] depended on dp[b] and dp[b] depended on dp[a], neither could be computed without the other — a circular definition. (Bellman equations on infinite-horizon Markov decision processes get around this with iterative methods like value iteration, but that’s outside the scope of competitive DP.)

11. Pitfalls

11.1 Wrong base case

The single most common DP bug. dp[0] = 0 is not always right; sometimes it is dp[0] = 1 (number of ways to make change for 0 cents — exactly one way: the empty set), or -∞ (longest path), or +∞ (shortest path with no path yet). Read the problem and ask “what is the answer for the empty subproblem?“

11.2 Iteration order wrong

In tabulation, if you fill dp[i] before its dependencies are populated, you read garbage (uninitialized or stale). For 01 Knapsack with the 1D rolling array, iterating capacity w in increasing order would let an item be picked twice — you must iterate w in decreasing order. This is the textbook DP gotcha.

11.3 In-place update bugs

When you collapse a 2D dp[i][j] to a 1D dp[j], you are reusing the same array for round i and round i-1. Whether dp[j] currently holds the old value or the new value depends on iteration order. Get this wrong and the recurrence silently corrupts itself.

11.4 Off-by-one in state definitions

Is dp[i] “first i items” (then dp[0] = empty) or “the i-th item” (then dp[0] = first item)? Pick a convention and stick to it. The most common convention is the former (dp[i] = answer for the prefix of length i), with dp[0] as the empty base case.

11.5 Memoizing on mutable arguments

@lru_cache requires arguments to be hashable. Passing a list as an argument fails immediately. Convert to a tuple, or memoize on indices into the list rather than the list itself. (The second is almost always preferable: smaller cache key, faster hash.)

11.6 Stack overflow on deep memoization

Python’s default recursion limit is 1000. Memoizing a recurrence with depth > 1000 (e.g., LIS on a 10⁵-length array) crashes. Either sys.setrecursionlimit(10**6) and enlarge the OS stack with threading.stack_size(...), or just write tabulation.

11.7 Forgetting to reconstruct

dp[final_state] is the value of the optimum, not the optimum itself. If the problem asks “which items did you pick?”, you need to backtrack through the table or store explicit predecessors during the fill. Many interviews ask for both the value and the witness — be ready.

11.8 Confusing DP with greedy

Greedy commits to a local choice and never reconsiders. DP enumerates choices and picks the best. If you can prove a greedy works (exchange argument, matroid structure), use it — it’s simpler. Otherwise default to DP. A common interview trap: an algorithm that looks greedy is actually DP because the greedy decision depends on a precomputed table.

11.9 State space too large

If n × m × k = 10^9, your DP table doesn’t fit in memory. Either find a smaller state, exploit sparsity, switch to bitmask DP (compress one dimension into a bitmask of size up to 20 or so), or look for structural properties that let you skip states (Knuth’s optimization, divide-and-conquer DP).

11.10 Memoization on infinite state spaces

If the recurrence can recurse into states with negative or unbounded indices, the cache grows without bound and the recursion may not terminate. Always validate: are all recursive calls strictly toward the base cases?

12. Diagram — The Subproblem DAG

flowchart TD
    F5[fib 5] --> F4[fib 4]
    F5 --> F3a[fib 3]
    F4 --> F3b[fib 3]
    F4 --> F2a[fib 2]
    F3a --> F2b[fib 2]
    F3a --> F1a[fib 1]
    F3b --> F2c[fib 2]
    F3b --> F1b[fib 1]
    F2a --> F1c[fib 1]
    F2a --> F0a[fib 0]
    F2b --> F1d[fib 1]
    F2b --> F0b[fib 0]
    F2c --> F1e[fib 1]
    F2c --> F0c[fib 0]

What this diagram shows. The recursion tree of naive fib(5) if no caching were applied. Many subproblems repeat: fib(3) appears twice, fib(2) three times, fib(1) five times, fib(0) three times. The total number of nodes grows as O(φ^n) where φ ≈ 1.618. Memoization keeps the same recursion-shaped traversal but assigns each distinct label fib(k) a single cache slot — the second visit returns instantly. Tabulation flips the picture entirely: it bypasses the tree and just walks fib(0), fib(1), fib(2), ..., fib(5) left-to-right in an array. Both reduce the work to one computation per distinct label, i.e., O(n). Visualizing this DAG is the single best mental tool for spotting overlapping subproblems in any new DP problem — if you can sketch the DAG and see repeats, you have a DP.

13. Common Interview Problems

Problem	LeetCode #	Pattern
Fibonacci Number	LC 509	Linear DP, depth-2 look-back
Climbing Stairs	LC 70	Identical recurrence to Fibonacci
House Robber	LC 198	Linear DP, take-or-skip choice
Coin Change	LC 322	Unbounded-knapsack flavor
Longest Common Subsequence	LC 1143	2D string DP — see Longest Common Subsequence
Edit Distance	LC 72	2D string DP — see Edit Distance
0/1 Knapsack	LC 416 (subset-sum reduction)	2D DP — see 01 Knapsack
Longest Increasing Subsequence	LC 300	Sequence DP — see Longest Increasing Subsequence
Unique Paths	LC 62	Grid DP, count paths
Word Break	LC 139	Boolean DP over string prefixes

Every one of these is a five-step-recipe exercise.

14. Open Questions

• When does converting a memoized DP to iterative tabulation hurt readability enough to not be worth it? Heuristic: if the topological order requires non-trivial reasoning, keep memoization.
• Knuth’s optimization, divide-and-conquer DP, and SOS DP — at what level of interview do these appear? Generally only competitive-programming territory; FAANG interviews rarely require them.
• When is policy/value iteration on a Bellman equation called “DP” vs called “reinforcement learning”? The line is fuzzy; both names refer to the same fixed-point iteration (see Bellman 1957 vs Sutton & Barto).

15. See Also

• 01 Knapsack — the canonical 2D DP with rolling-array optimization
• Longest Common Subsequence — 2D DP on two strings
• Edit Distance — closely related to LCS; also 2D string DP
• Longest Increasing Subsequence — sequence DP with O(n log n) variant
• Bellman-Ford — DP over (vertex, edge-budget); the graph-shaped DP
• Recursion vs Iteration — relevant for memoization stack depth concerns
• Big-O Notation — counting states × transitions
• SWE Interview Preparation MOC