Dynamic Programming: Memoization as Optimization

Dynamic programming sounds intimidating — the technique is boring once you see it: when a recursive solution recomputes the same subproblems, cache them. That's memoization. The trick is recognizing which problems have overlapping subproblems.

The Fibonacci example

# exponential: recomputes fib(n-2) twice, fib(n-3) four times, ...
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

# O(n) with memoization — each subproblem computed once
from functools import cache
@cache
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

The @cache decorator (or a dict) makes overlapping recursion linear. The same pattern applies to any recursive problem where subproblems repeat: counting paths, edit distance, knapsack.

Top-down vs bottom-up

Top-down (memoization) — write the natural recursion, add a cache. Easier to write; pays recursion overhead and can hit stack depth limits.

Bottom-up (tabulation) — fill a table iteratively, smallest subproblems first. No recursion; often faster; harder to see the structure.

# bottom-up fib — iterative, O(1) space
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

The DP pattern

1. Define dp[i] = the answer for the subproblem of size i.
2. Write the recurrence: dp[i] = f(dp[i-1], dp[i-2], ...).
3. Fill base cases, then iterate in dependency order.
4. The answer is dp[n] — or a max/min over dp.

Field notes

• If the recursion doesn't overlap, DP isn't needed — O(n) recursion is fine without memoization.
• The space optimization (dp[i-1] only) is often the real win — dp tables can be huge; reduce to a rolling window when only the last few states matter.