Memoization: Top-Down DP

"Memoization is the gentlest way into dynamic programming: write the obvious recursion, then add a cache. Often it's a one-line change that turns an exponential disaster into a linear-time solution."

Recursion Plus a Cache

Memoization is top-down DP: you write the natural recursive solution — the one that directly mirrors the problem — and add a cache that remembers each subproblem's answer the first time it's computed. Every later request for that same subproblem is an instant lookup instead of a recomputed subtree. It's called top-down because you start at the big problem and recurse down toward the base cases, caching results as the recursion unwinds. The beauty: you don't have to redesign anything — you take a correct (but slow) recursion and make it fast by remembering.

The Cache Key Is the State

A cache key must contain the complete immutable state that determines the answer. Function arguments are suitable only when the function is effectively pure and does not hide relevant mutable or external state. @functools.cache automates storage for hashable arguments; it does not prove that the chosen state is complete.

Memoization = a natural recursion + a cache keyed by the subproblem's state (its arguments). It's top-down (start big, recurse down, cache on the way). In Python, @functools.cache turns a correct recursion into DP in one line. It only computes the subproblems you actually reach (lazy).

The Trade-Offs

Memoization's strengths: it's the easiest DP to write (just cache a recursion you already trust), and it's lazy — it only ever computes the subproblems actually needed to answer your query, skipping unreachable states a bottom-up table would waste time filling. Its weaknesses: it rides the call stack, so very deep state chains can hit the recursion limit (the Recursion-track caution), and the cache carries some memory and lookup overhead. For most problems, memoization is the right first move — reach for the bottom-up table (next lesson) only when depth or space forces it.

Pippa's Confession

The first time I 'did DP,' I expected to rewrite everything into some unfamiliar table-filling shape. Dad just typed @cache above my existing recursive function and it went from timing out to instant. I felt slightly cheated — that's dynamic programming? But that's the honest truth of top-down DP: if your recursion is correct, memoization is often a single decorator away. The hard part was never the caching; it was writing the right recurrence, which I'd already done.

Code

Coin change as top-down memoized DP·python

from functools import cache

# COIN CHANGE (fewest coins to make `amount`), top-down memoized.
# State = the remaining amount; that's the cache key.
def coin_change(coins, amount):
    @cache
    def fewest(remaining):                # 'remaining' is the subproblem STATE
        if remaining == 0:
            return 0                       # base case: 0 coins to make 0
        if remaining < 0:
            return float('inf')            # overshot — impossible
        # try every coin; take the best (fewest-coins) option, +1 for this coin
        return min(fewest(remaining - c) + 1 for c in coins)
    result = fewest(amount)
    return result if result != float('inf') else -1

print(coin_change([1, 3, 4], 6))   # 2  (3 + 3, not greedy's 4+1+1 = 3 coins)
# Note: greedy 'take the biggest coin' gives 4+1+1 = 3 coins — WRONG.
# DP reuses fewest(remaining) across the recursion: the same subproblems repeat,
# @cache computes each once. Correct recursion + one decorator = top-down DP.

Exercise

You have a recursive function climb(n) = climb(n-1) + climb(n-2) that counts the ways to climb n stairs taking 1 or 2 steps at a time (base: climb(0)=climb(1)=1). It's exponential as written. Add memoization and state what the cache key is. Why does caching collapse it to O(n), and what's the 'state' of each subproblem?

Hint

The state is just n (the number of remaining stairs), so the cache key is n. Decorate with @cache: each climb(k) computes once, every repeat is O(1), and there are only n distinct states → O(n) total instead of O(2ⁿ). It's the Fibonacci pattern wearing a staircase.

Recursion Plus a Cache

The Cache Key Is the State

The Trade-Offs

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0