One habit, kept honestly
The last guide left us staring at a recursion tree that solved the same subproblem astronomically many times — fib(5) calling fib(3) twice, fib(2) three times, and so on, the repeats multiplying as the tree deepens. That repetition is the whole disease, and memoization is the whole cure. The recipe is almost embarrassingly simple: before computing the answer to a subproblem, check whether you have already computed it; if so, return the stored value; if not, compute it the usual recursive way, store it, then return it. Nothing about the recursion's logic changes — you only add a notebook beside it.
This is what people mean by top-down dynamic programming. 'Top-down' because you still start at the original question — fib(n), the longest path, the cheapest cut — and let the recursion ask for whatever smaller pieces it needs, on demand. The word 'memoization' (no 'r' — from memo, a note to self) names exactly that notebook habit. It is the gentlest possible doorway into dynamic programming, because you keep your already-correct recursive function and bolt a cache onto it.
memo = {} # the notebook, empty at the start
function fib(n):
if n <= 1: return n # base cases, never cached
if n in memo: return memo[n] # already solved? hand it back
answer = fib(n-1) + fib(n-2) # otherwise solve it the usual way
memo[n] = answer # write it down before returning
return answerWhy the blow-up collapses
Here is the accounting that makes memoization more than a trick. Every call to fib(k) does one of two things: it is the first call with that k, in which case it does a constant amount of real work (one addition) and then fills in memo[k]; or it is a repeat call, in which case it does a constant amount of work too (one lookup, one return) and recurses no further. So divide all the calls into two piles. The 'first' pile has at most one call per distinct value of k — that is at most n entries. The 'repeat' pile can be large, but each repeat is triggered by some first call making at most two recursive requests, so there are at most twice as many repeats as firsts.
Add the piles: total calls are O(n), each doing O(1) work once you ignore the recursion they delegate, so the whole computation is O(n) time. Compare that with the exponential roughly 1.618^n calls of the un-memoized version. The dramatic improvement comes from one structural fact the last guide named: there are only n+1 distinct subproblems here, fib(0) through fib(n), and naive recursion was paying to solve each of them an exponential number of times. Memoization charges for each distinct subproblem exactly once.
Tracing the cache fill
Watch fib(5) run with the notebook, so the savings stop being abstract. The first call fib(5) needs fib(4) and fib(3); fib(4) dives first and needs fib(3) and fib(2); that fib(3) needs fib(2) and fib(1); and the chain bottoms out at the base cases fib(1)=1 and fib(0)=0. As each call finally returns, it records its answer. Crucially, the very next time any value is requested, it is already in the notebook, so the request returns instantly without re-descending.
- The deep dive down the fib(4) side fills the notebook from the bottom up: memo gets fib(2)=1, then fib(3)=2, then fib(4)=3, as each call returns.
- Now fib(5) turns to its second child, fib(3). In naive recursion this would re-expand an entire subtree; here memo[3] already holds 2, so it returns at once — the whole repeated subtree is pruned to a single lookup.
- fib(5) computes fib(4) + fib(3) = 3 + 2 = 5, records memo[5]=5, and returns. Every distinct subproblem fib(0)..fib(5) was truly computed exactly once.
Notice the shape of what happened: the recursion tree, which was bushy and exponential, has been pruned into something no bigger than a thin path plus a sprinkling of instant lookups. The pruning is automatic — you never wrote code to recognize a repeat; the notebook check does it for you. That is the quiet elegance of the top-down style: you describe the problem recursively, in the way it most naturally decomposes, and the cache silently removes the redundancy.
What memoization quietly assumes
A cache is only safe if the answer to a subproblem never changes between the time you store it and the time you reuse it. That is the first of the two preconditions for DP: the problem must have overlapping subproblems (otherwise the cache never gets a hit and you have only added overhead), and it must have optimal substructure (the answer to a big problem is genuinely built from correct answers to fixed smaller ones). Memoization leans hard on a third, often-unspoken assumption hiding inside both: a subproblem's answer is a pure function of its arguments — same inputs, same output, always.
There is also a real-machine caveat the asymptotics hide. Top-down memoization keeps the call stack as deep as the longest chain of dependencies — fib(n) recurses n deep — so on a long, thin recursion it can overflow the stack even though it is fast on paper. And the notebook itself costs memory: O(number of distinct subproblems) of it. These are honest costs, not deal-breakers, but they are exactly the kind of thing Big-O time sweeps under the rug, and they are the practical reason the next guide reaches for the bottom-up alternative.
From the value to the actual solution
Memoization, as written, returns a number — the length of the longest path, the minimum cost, the maximum value. But you usually want the thing: which path, which items, which cuts. The cache alone does not tell you that; it stores answers, not the choices that produced them. The standard move is reconstructing the solution after the values are filled in. You start at the top state and, at each step, look at the candidate choices the transition considered and ask which one actually achieved the stored optimum, then follow that choice into its subproblem and repeat.
Concretely, for a problem where best(s) = min over choices c of (cost(c) + best(next(s, c))), reconstruction re-scans the choices at state s, finds the c whose right-hand side equals the stored best(s), records that c as part of the answer, and moves to next(s, c). Because the values are already cached, each of these checks is a cheap lookup, so reconstruction costs roughly one pass down the chain of states on the optimal solution — far cheaper than the original fill. An alternative is to store, alongside each cached value, a pointer to the choice that achieved it; then reading off the solution is just following those pointers, with no re-scan at all.
Keep the two phases mentally separate: the fill phase computes the optimal value of every reachable state (and is where all the asymptotic cost lives), while reconstruction merely walks one optimal path through those values to recover the witness. This split is general — it is just as true for the bottom-up style of the next guide — and it is the cleanest way to think about every classic DP, from the longest common subsequence to edit distance to knapsack, which the closing guides of this rung work through in full.