Memoization vs Tabulation

Once you've identified a DP problem and defined your state and recurrence, you face one more question: how do I actually compute this? There are two approaches, and they're like two different personalities.

Memoization (top-down): Start at the big problem. Recurse down. If you've already solved a sub-problem, return the cached answer immediately. Otherwise, solve it, cache it, return it. Like calling a friend — who might call another friend — who might call someone else. Eventually the chain bottoms out, and answers propagate back up.

Tabulation (bottom-up): Start at the smallest sub-problems. Fill a table from smallest to largest, ensuring each cell's dependencies are already filled in. Like filling in a spreadsheet: each cell uses already-computed cells to its left or above. No recursion, no call stack.

Both give the same asymptotic time and space. The choice is about practical tradeoffs.

Memoization — The Lazy Approach

Write the recursive solution exactly as the recurrence says, then add a cache check at the top.

Advantages:
• Natural to write — the code mirrors the recurrence directly.
• Lazy: only computes sub-problems actually needed. If your solution only touches a small fraction of the state space, memoization avoids the wasted work tabulation would do.
• Easy to implement with Python's @lru_cache, JavaScript closures, or a dictionary.

Disadvantages:
• Function call overhead and call-stack memory.
• Stack overflow risk: if n=1,000,000 and each recursive call adds one frame, most systems' default call stack (typically 1,000–10,000 frames) will overflow.
• Space optimization (rolling arrays) is harder to apply — the recursive structure makes it non-obvious which cached states you can discard.

Tabulation — The Eager Approach

Determine the correct fill order (usually smallest-index to largest), iterate, and fill each cell.

Advantages:
• No recursion overhead, no stack overflow.
• Fill order is explicit — you can often optimize space by discarding old rows (rolling window), reducing \(O(n^2)\) to \(O(n)\) or \(O(n)\) to \(O(1)\).
• Better cache locality in practice — sequential array access is fast.

Disadvantages:
• Determining the correct fill order can be non-obvious for 2D or irregular DP.
• Computes all sub-problems, even those not needed for the final answer.

Space Optimization — Tabulation's Superpower

Many DP recurrences look only one or two rows back. When that's the case, you can throw away older rows and keep only what you need.

Fibonacci: dp[i] = dp[i-1] + dp[i-2]. Only need the last two values. Space: \(O(n)\) → \(O(1)\).

0/1 Knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val). Only need the previous row. Space: \(O(n·W)\) → \(O(W)\). (Iterate w in reverse to avoid overwriting values you still need.)

This optimization is straightforward with tabulation. With memoization, you'd need to manually track which cached states are still needed — much harder.

Memoization vs Tabulation — Fibonacci & 0/1 Knapsack

from functools import lru_cache

# === FIBONACCI ===
# Top-down memoization
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# Bottom-up tabulation (space-optimised to O(1))
def fib_tab(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b

print(f"Fib(10) memo: {fib_memo(10)}, tab: {fib_tab(10)}")

# === 0/1 KNAPSACK ===
# Top-down memoization
def knapsack_memo(weights, values, capacity):
    @lru_cache(maxsize=None)
    def dp(i, w):
        if i == 0 or w == 0: return 0
        if weights[i-1] > w:
            return dp(i-1, w)
        return max(dp(i-1, w), dp(i-1, w-weights[i-1]) + values[i-1])
    return dp(len(weights), capacity)

# Bottom-up tabulation (space-optimised: one row O(W))
def knapsack_tab(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w-1, -1):  # reverse to avoid overwrites
            dp[c] = max(dp[c], dp[c-w] + v)
    return dp[capacity]

wt = [2, 3, 4, 5]
val = [3, 4, 5, 6]
cap = 8
print(f"Knapsack memo: {knapsack_memo(wt, val, cap)}")
print(f"Knapsack tab:  {knapsack_tab(wt, val, cap)}")

Output

Fib(10) memo: 55, tab: 55
Knapsack memo: 10
Knapsack tab:  10

Complexity

⏱️ Memoization time

Cache hit returns instantly; total work = number of distinct states × transition cost

Each state computed once \(O(states)\)

📚 Memoization space

Recursion depth adds \(O(n)\) stack frames — risk of stack overflow for large n

Cache + call stack \(O(states + depth)\)

⏱️ Tabulation time

Same asymptotic time; often faster in practice due to no function call overhead

Fill entire table \(O(states)\)

📦 Tabulation space (full table)

Stores every computed value — necessary if all values are needed later

All states stored \(O(states)\)

✂️ Tabulation space (rolling window)

When recurrence only looks back a fixed number of rows — discard the rest

Previous row(s) only \(O(1)\) to \(O(row size)\)

Memoization — The Lazy Approach

Tabulation — The Eager Approach

Space Optimization — Tabulation's Superpower

Memoization vs Tabulation — Fibonacci & 0/1 Knapsack

Complexity

Quick check