Intro to Dynamic Programming: Memoization

"Dynamic programming" sounds like a heavyweight technique reserved for competitive programmers. It isn't. It's one small, almost embarrassing observation: if you're about to compute something you already computed, don't. Write the answer down the first time and look it up after. Apply that to the right recursive function and an algorithm that would take longer than the age of the universe finishes instantly.

The blow-up: naive Fibonacci

The Fibonacci sequence is the standard first example because its naive recursion is a perfect trap. Each number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. Translate that straight into code and you get something that looks innocent:

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

It's correct. It's also a disaster, and the reason is overlapping subproblems. To compute fib(5) you compute fib(4) and fib(3). But fib(4) also needs fib(3). So fib(3) gets computed twice, and each of those recomputes fib(2), and so on. The same little subproblems get solved over and over, an exponential number of times.

Here's the call tree for fib(5). Count how many times fib(2) shows up:

fib(3) is computed twice. fib(2) three times. Each subtree is fully recomputed from scratch every time it appears, with no memory that it just did this. The number of calls roughly doubles for every +1 in n, which is O(2ⁿ), and it's why fib(50) naively would grind for ages.

Watch the explosion live. This is the naive fib running its full call stack for n = 6:

Every one of those calls is real work, and most of it is repeated work.

Memoization: write the answer down

Memoization (top-down DP) fixes this with a cache. Before computing fib(n), check whether you've already solved it. If yes, return the stored answer. If no, compute it once, store it, then return it. The recursion is identical. You just bolt on a memory.

Now fib(3) is computed exactly once. The second time the tree asks for it, the answer is already sitting in the cache, so the entire subtree underneath that second fib(3) never runs. Whole branches of the call tree get pruned to a single lookup.

Here's the same fib(6), memoized:

Side by side with the naive version, the difference is stark. Each distinct subproblem (fib(0) through fib(6)) gets solved exactly once, and every other reference is a cheap cache hit. You've turned O(2ⁿ) into O(n): one real computation per value of n, full stop.

Both versions, with a call counter

Run this to see it in numbers. It counts how many times each function actually does work, for the same n. Push n up to 30 and watch the gap explode.

For n = 20 the naive version makes over 13,000 calls. The memoized one makes around 40. The logic is byte-for-byte the same recursion. The only addition is "check the cache, store the result." And functools.lru_cache does exactly that for you, no manual dict required, which is how you'd actually write it in production.

A nod to tabulation

Memoization is top-down: you start at fib(n) and recurse down, caching as you go. The other flavour of DP is tabulation (bottom-up): start at the smallest subproblems and build up to the answer with a loop, filling a table.

def fib_table(n):
    if n < 2:
        return n
    table = [0, 1]
    for i in range(2, n + 1):
        table.append(table[i - 1] + table[i - 2])
    return table[n]

Same O(n), no recursion, no call-stack depth to worry about. Memoization is usually easier to write (decorate the recursion and you're done). Tabulation can be faster and avoids deep recursion limits. Both are dynamic programming, two routes to the same idea of solving each subproblem once.

Where to go next

Dynamic programming is one habit: spot overlapping subproblems, then stop recomputing them. Memoization caches a recursive function top-down, while tabulation builds the table bottom-up. Either way, the same insight that turns exponential Fibonacci into linear Fibonacci scales to far harder problems (shortest paths, edit distance, knapsack) wherever the same subproblem keeps showing up.

Time to put the whole series to work. Next: Project: Build an LRU Cache, a real, O(1) cache that combines a hash map with ordering, and a caching idea you just used here. If the recursion underneath all this needs a refresher, revisit Recursion & the Call Stack.