Memoization vs Tabulation: Top-Down vs Bottom-Up DP

Every dynamic programming solution can be written two ways. Memoization (top-down) keeps the recursive function and caches its answers. Tabulation (bottom-up) throws the recursion away and fills a table from the base cases forward. Interviewers ask "memoization vs tabulation?" because the honest answer is not "tabulation is faster": each has a real advantage, and knowing which one to reach for, and how to convert between them, is what separates a memorised solution from an understood one.

The problem it solves

Dynamic programming applies when a problem breaks into subproblems that overlap: the same smaller question is asked again and again. Plain recursion recomputes every repeat. Fibonacci is the standard example: fib(25) by naive recursion makes 242,785 calls to compute 26 distinct values.

Both techniques fix that by computing each subproblem once. They differ in direction:

• Top-down starts at the question you were asked, recurses into what it needs, and stores each answer in a memo on the way back up.
• Bottom-up starts at the base cases and fills a table in an order where every value's dependencies are already written.

The recurrence, the part that takes thought, is identical. Only the order of evaluation changes.

The intuition

Think of the subproblems as a graph: an arrow from each state to the states it needs. Top-down explores that graph from the goal, lazily, touching only the states reachable from it. Bottom-up walks it in a fixed order, eagerly, touching every state in the table whether or not the answer depends on it.

That gives each side its advantages:

• Top-down is easier to write. You derive the recurrence as a recursive function first anyway; adding a cache is two lines. It also skips states the answer never needs, which matters when the reachable states are sparse.
• Bottom-up has no recursion. No stack frames, no recursion-depth limit, no function-call overhead. And because it fills rows in a known order, you can often keep only the last row or two, cutting space from O(n) to O(1).

The practical rule: write the recursion, memoize it to get a correct answer, then convert to a table if depth or memory becomes a problem. The conversion is mechanical once you know which states each state reads.

Watch it run

The animation solves fib(4) both ways. Top-down starts at the full problem, fib(4), and recurses only into what it actually needs. It descends into fib(3), then fib(2), then the base cases, and every pending call holds a stack frame open. fib(1) = 1 and fib(0) = 0 return without recursing: the base cases stop the descent. fib(2) = 1 comes back and is written to the memo on the way up. The second fib(2) is now a cache hit, so that entire branch is never executed. fib(3) = 2, then fib(4) = 3, and only the subproblems actually needed were ever touched. Bottom-up throws the recursion away and writes the base cases into the table directly, table[0] = 0 and table[1] = 1. Then table[2] = table[1] + table[0], table[3], table[4], each time with both dependencies written before they were read. No recursion, so no stack to blow, but it fills every entry whether the answer needs it or not. One recurrence, two directions: top-down is easier to derive from the recursion; bottom-up never leaves a call frame open.

The code

The lesson's two versions, plus naive recursion, with a counter to show what the memo saves:

calls = 0

def naive(n):
    global calls
    calls += 1
    return n if n < 2 else naive(n - 1) + naive(n - 2)

def top_down(n, memo):
    global calls
    calls += 1
    if n < 2:
        return n
    if n not in memo:                                  # solve on demand
        memo[n] = top_down(n - 1, memo) + top_down(n - 2, memo)
    return memo[n]

def bottom_up(n):
    table = [0, 1] + [0] * (n - 1)                     # base cases first
    for i in range(2, n + 1):                          # dependency order
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

calls = 0
print(naive(25), calls)          # 75025 242785
calls = 0
print(top_down(25, {}), calls)   # 75025 49
print(bottom_up(25))             # 75025

Bottom-up's two advantages in action. Each entry reads only the two before it, so two variables replace the table. And a deep input breaks the recursive version on Python's default recursion limit while the loop does not notice:

def rolling(n):
    a, b = 0, 1                                        # only two rows are ever read
    for _ in range(n):
        a, b = b, a + b
    return a

try:
    top_down(5000, {})
except RecursionError:
    print("RecursionError")      # RecursionError
print(bottom_up(5000) == rolling(5000), len(str(rolling(5000))))   # True 1045

Top-down's advantage: sparse states. Here a value n is worth either n itself or the best of splitting it into n // 2, n // 3 and n // 4. From one million, the memo touches 108 distinct values; the table fills a million entries to get the same answer:

from functools import lru_cache

@lru_cache(maxsize=None)
def best(n):                                           # exchange n, or split it three ways
    return max(n, best(n // 2) + best(n // 3) + best(n // 4)) if n else 0

def best_table(n):
    t = [0] * (n + 1)
    for i in range(1, n + 1):
        t[i] = max(i, t[i // 2] + t[i // 3] + t[i // 4])
    return t[n]

print(best(1_000_000), best.cache_info().currsize)   # 2566393 108
print(best_table(1_000_000))                          # 2566393

Every version against the naive recursion as the brute force, and the sparse pair against each other, on random inputs:

import random

random.seed(21)
ok = True
for _ in range(300):
    n = random.randint(0, 22)
    ok &= naive(n) == top_down(n, {}) == bottom_up(n) == rolling(n)
for _ in range(300):
    n = random.randint(0, 3000)
    ok &= best(n) == best_table(n)
print(ok)                        # True

The complexity

• Time: both are the number of states times the work per state, O(n) for Fibonacci. Top-down pays a function call and a hash lookup per state; bottom-up pays a list index.
• Space: both store O(states). Top-down adds a call stack as deep as the longest dependency chain. Bottom-up can often drop to the last few rows, O(1) here.
• States touched: top-down only the reachable ones, bottom-up all of them. For the split problem that is 108 against a million.

Where it goes wrong

• A mutable default memo. def f(n, memo={}) shares one dictionary across unrelated calls, so answers leak between test cases.
• Caching on the wrong key. If the answer depends on two parameters, the memo key must include both.
• Filling the table in the wrong order. Bottom-up only works if every dependency is written first; in 2-D problems that decides whether loops run forwards or backwards.
• Rolling variables too early. Keep the full table until the answer is right, especially if you must reconstruct the choices, not just the value.
• Assuming recursion depth is free. A chain of 10,000 states needs the iterative version in Python.

When it shows up in interviews

Almost every DP question invites it: climbing stairs and house robber are usually memoized first and rolled into two variables second, and coin change and longest common subsequence are usually tabulated. It also underlies backtracking vs dynamic programming: memoization is what turns a search with repeated states into DP. The 1-D problems are grouped on the patterns cheat sheet.

How to say it in an interview

"Both use the same recurrence and solve each subproblem once. Top-down is the recursive function plus a cache: it is the fastest to write and only touches the states the answer needs, but it uses the call stack, so very deep inputs can hit the recursion limit. Bottom-up fills a table from the base cases in dependency order: no recursion, less overhead, and I can usually keep only the last row, so space drops to O(1) here. I would start top-down to get the recurrence right, then convert to bottom-up if depth or memory matters, or stay top-down if the reachable states are sparse."