Memoization vs. Tabulation

Jr Codex DSA Notes

Level: Advanced Prerequisites: Module 9, Chapter 4 Time to complete: ~30 minutes

Table of Contents

1. Why Naive Recursion Can Be Slow
2. Overlapping Subproblems — the Root Cause
3. Top-Down: Memoization
4. Using functools.lru_cache
5. Bottom-Up: Tabulation
6. Memoization vs. Tabulation — Tradeoffs
7. The General DP Recipe
8. Summary & Next Steps

1. Why Naive Recursion Can Be Slow

Back in Module 1, Chapter 2, you saw naive recursive Fibonacci flagged as O(2ⁿ):

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

For n = 5, this doesn't feel slow. For n = 40, it takes noticeably long. For n = 100, it will not finish in your lifetime. Dynamic programming exists to fix exactly this class of problem — and the fix doesn't require a different algorithm, just a smarter way of running the same recursive idea.

2. Overlapping Subproblems — the Root Cause

Draw the recursion tree for fib_naive(5) (as introduced conceptually in Module 4, Chapter 2) and a pattern jumps out: fib_naive(3) gets computed twice, fib_naive(2) gets computed three times, and so on. The function keeps re-deriving answers it has already computed.

                    fib(5)
                 /          \
             fib(4)          fib(3)
            /      \         /      \
        fib(3)    fib(2)  fib(2)   fib(1)
        /    \     /  \    /  \
    fib(2) fib(1) fib(1)fib(0) fib(1) fib(0)

This property — overlapping subproblems — is the signal that a problem is a DP candidate. (The other required property, optimal substructure, means the optimal answer to the whole problem can be built from optimal answers to its subproblems — true here since fib(n) is defined directly in terms of fib(n-1) and fib(n-2).) If neither property holds, memoizing won't help — there's nothing to reuse.

3. Top-Down: Memoization

Memoization keeps the exact same recursive structure, but caches each subproblem's answer the first time it's computed, so repeat calls return instantly instead of re-deriving the answer:

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]           # already solved — O(1) lookup
    if n <= 1:
        return n
 
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Now each value from 0 to n is computed exactly once. Time complexity drops from O(2ⁿ) to O(n) — every subproblem does O(1) work beyond its (cached) recursive calls. Space complexity is O(n) for the cache, plus O(n) for the recursion call stack (Module 1, Chapter 4) — still O(n) overall, but a real cost worth naming.

This is called top-down because you start at the original problem (fib(n)) and recurse down toward the base cases, caching along the way.

4. Using functools.lru_cache

Python's standard library provides a decorator that does exactly this caching for you, with no manual dictionary:

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)
    # Same O(n) time as the manual cache — lru_cache handles memoization
    # automatically based on the function's arguments.

lru_cache is the pragmatic default for interview settings and quick scripts. The manual-dictionary version in Section 3 is worth knowing because it generalizes to cases where the cache key isn't just the function's arguments (e.g., caching on a mutable derived state).

5. Bottom-Up: Tabulation

Tabulation flips the direction: instead of starting at fib(n) and recursing down, you start at the base cases and iteratively build up to fib(n), storing each result in a table (often just a list or a couple of variables) as you go.

def fib_tabulation(n):
    if n <= 1:
        return n
 
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]
    # O(n) time, O(n) space for the table

Since each fib(i) only ever needs the previous two values, the table can be compressed to two variables:

def fib_optimized(n):
    if n <= 1:
        return n
 
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
    # O(n) time, O(1) space — no recursion stack, no growing table

This last version is strictly better than every memoized version above on space, precisely because tabulation has no call stack and, here, doesn't even need the full table — only recursion inherently requires stack space.

6. Memoization vs. Tabulation — Tradeoffs

Neither is universally "better." Memoization is usually the faster path to a correct solution because it mirrors the recursive definition directly. Tabulation is usually the better final solution for production code, since it avoids recursion-depth limits and often reduces space further, as shown above.

7. The General DP Recipe

Every DP problem in this module follows the same steps:

1. Write the naive recursive solution first, even if it's exponential — it's the clearest way to express what the problem is asking.
2. Identify the recursive relationship (how does the answer to n depend on smaller subproblems?).
3. Confirm overlapping subproblems exist (would the same subproblem get solved more than once?).
4. Add memoization (a cache dict or @lru_cache) — this alone usually fixes the exponential blowup.
5. Optionally convert to tabulation if you want to avoid recursion depth limits or shrink space further.

Chapters 2 and 3 apply this recipe to progressively harder problems.

8. Summary & Next Steps

Key Takeaways

• DP applies when a problem has overlapping subproblems and optimal substructure — without both, memoizing does nothing.
• Memoization (top-down) caches a recursive solution's results; tabulation (bottom-up) iteratively builds the answer from the base cases up.
• Both typically bring naive exponential recursion down to O(n) or O(n²) — the specific improvement depends on the problem.
• Tabulation avoids recursion-stack space entirely and can sometimes compress further (as with Fibonacci's O(1)-space version); memoization is often faster to write correctly on the first try.

Concept Check

1. What two properties must a problem have for DP to help at all?
2. Why does memoized Fibonacci still use O(n) space, even though the exponential blowup is gone?
3. Why can the tabulated Fibonacci solution be compressed to O(1) space, but the memoized version generally can't?

Next Chapter

→ Chapter 2: Classic 1D DP

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index