Dynamic programming — from recursion to tabulation

DP isn't a separate topic from recursion — it's memoized recursion, and the "bottom-up" version most people find intimidating is the exact same idea, just computed in the opposite direction.

Advanced

4 min read

The problem DP actually solves: overlapping subproblems

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

Naive recursive Fibonacci is exponential — fib(5) calls fib(3) twice, fib(2) three times, recomputing the exact same values over and over. The recursion lesson already covered why this shape happens; dynamic programming is specifically the technique for when that repeated work is the same subproblem being solved again and again. If subproblems don't overlap (each is genuinely distinct), memoizing them buys nothing — DP only pays off when the same subproblem recurs.

Top-down: recursion plus a cache

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

This is memoization, already covered in the recursion lesson — store each subproblem's result the first time it's computed, return the cached value on every subsequent call for that same input. It turns fib's exponential blowup into O(n): each of the n distinct subproblems gets computed exactly once. This is dynamic programming — "top-down DP" is just another name for memoized recursion.

Bottom-up: the same computation, built forward instead of unwound backward

def fib(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]   # build from the base cases up
    return table[n]

Instead of starting at fib(n) and recursing down to the base cases, tabulation starts at the base cases and builds up to fib(n) directly, in a loop — no recursion, no call stack, no risk of hitting Python's recursion limit on large n. It computes the exact same set of subproblems as the memoized version, in the reverse order: bottom-up doesn't discover which subproblems it needs by recursing into them, so it has to compute every subproblem from the base case forward, in an order where each one's dependencies are already filled in before it's needed.

Why bottom-up is usually the better default once the recurrence is clear

The recursion lesson noted Python doesn't optimize tail calls, so deep recursion risks RecursionError — tabulation sidesteps that entirely, since it's an ordinary loop. It's also frequently more memory-efficient: fib's bottom-up version only actually needs the previous two values, not the whole table, letting it drop to O(1) space:

def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

This space optimization — collapsing a full table down to just the entries a later step actually depends on — only works cleanly once you can see the recurrence explicitly, which is easier to reason about in the bottom-up form than by staring at recursive calls.

The actual DP workflow, in order

Write the naive recursive solution first. Get the recurrence relation right — how does the answer for n depend on smaller subproblems — before worrying about efficiency at all.
Identify the overlapping subproblems. Confirm the same subproblem really does recur; if it doesn't, DP isn't the right tool.
Add memoization (top-down) as the mechanical first optimization — usually a small, low-risk change to code that already works.
Convert to tabulation (bottom-up) if recursion depth or the recursive call stack's overhead actually matters for the input sizes involved — this is an optional further step, not a required one.

Skipping straight to a bottom-up table without first getting the recurrence right from the naive recursive version is where most DP mistakes actually come from — the loop version is harder to reason about directly than the recursive one, precisely because the recursive version's structure IS the recurrence relation, made visible.