Memoization (top-down DP) — recursive + memo dict: Worked examples

Before anything, a promise about vocabulary. A state is the complete description of a subproblem — the set of argument values that fully decides its answer. A memo (or cache) is a dictionary whose key is that state and whose value is the already-computed answer. Everything on this page is: pick the state, write the recurrence, cache by the state, store before returning.

The scenario matrix

Every memoization problem lives in one of these cells. The examples underneath are labelled with the cell they cover.

#	Case class	What is new / tricky	Covered by
A	1-D state, 2-way branch	the textbook shape	Ex 1
B	Base case at zero (degenerate input)	what does `n = 0` mean?	Ex 1, Ex 2
C	1-D state, k-way branch	recurse over a loop, not two fixed calls	Ex 3
D	2-D state (tuple key)	key must hold both variables	Ex 4
E	Negative / out-of-range state	guard before you index	Ex 5
F	Choice = max/min, not sum	`combine` is not always `+`	Ex 6
G	Real-world word problem	translate English → recurrence	Ex 7
H	Exam twist: stale-key bug	why a wrong key silently lies	Ex 8
I	Limiting behaviour / complexity	count distinct states	Ex 9

Ex 1 — Fibonacci at a boundary (cells A, B)

Worked example Compute

$F (6)$ with the memoized recurrence $F (n) = F (n - 1) + F (n - 2)$ , $F (0) = 0$ , $F (1) = 1$ . Also state what $F (0)$ means.

Forecast: guess $F (6)$ before reading. (Sequence: $0, 1, 1, 2, 3, 5, \dots$ )

Write the states we will touch. Starting from $6$ , the distinct states are ${0, 1, 2, 3, 4, 5, 6}$ — seven of them. Why this step? Memoization's whole speed claim is "one computation per distinct state." Listing them first tells us the cache will hold at most 7 entries.
Fill smallest-first (this is what the recursion does, just ordered for us). $F (2) = F (1) + F (0) = 1 + 0 = 1$ . Why this step? The base values $F (0) = 0, F (1) = 1$ are given — they are the sticky notes we start with. Everything else is built on top.
Climb. $F (3) = 1 + 1 = 2$ ; $F (4) = 2 + 1 = 3$ ; $F (5) = 3 + 2 = 5$ ; $F (6) = 5 + 3 = 8$ . Why this step? Each line reads two earlier sticky notes and writes a new one — exactly $O (1)$ work per state.
Meaning of the degenerate input $F (0)$ . $F (0) = 0$ : there are zero "1s" to sum, so the empty sum is $0$ . The base case is a definition, not something you derive. Why this step? Cell B — the zero input — is where beginners guess wrong. Nail it explicitly.

Verify: the classic sequence $0, 1, 1, 2, 3, 5, 8$ has $F (6) = 8$ . ✓ Cache ended with exactly 7 keys ⇒ 7 computations, matching "distinct states."

Ex 2 — Climbing Stairs, why $W (0) = 1$ (cell B, contrast with Ex 1)

Worked example Ways to climb

$n = 5$ stairs taking 1 or 2 steps. $W (n) = W (n - 1) + W (n - 2)$ , $W (0) = 1$ , $W (1) = 1$ .

Forecast: same recurrence shape as Fibonacci but a different base value. Will the answer be $F (5) = 5$ ? Guess.

Compare the two base cases. Fibonacci: $F (0) = 0$ . Stairs: $W (0) = 1$ . Why this step? Cell B strikes again — the recurrence alone does not fix a DP; the base value is half the definition. One wrong number here poisons every state above it.
Justify $W (0) = 1$ . To "climb zero stairs" you do nothing — that is exactly one valid (empty) way, not zero. Why this step? The word problem's meaning decides the base value, and here "no moves" is still a way.
Compute. $W (2) = W (1) + W (0) = 1 + 1 = 2$ ; $W (3) = 2 + 1 = 3$ ; $W (4) = 3 + 2 = 5$ ; $W (5) = 5 + 3 = 8$ . Why this step? Straight cache-fill, smallest first.

Verify: with the shifted base, stairs give $2, 3, 5, 8$ for $n = 2..5$ — that is Fibonacci shifted by one, so $W (5) = F (6) = 8$ . ✓ (Same engine, different starting sticky note.)

Ex 3 — Coin-change count, a k-way branch (cell C)

Worked example Using coins

${1, 3, 4}$ (unlimited), how many ordered sequences sum to $n = 4$ ? Let $C (0) = 1$ , and $C (n) = \sum_{c \in {1, 3, 4}, c \leq n} C (n - c)$ .

Forecast: the branch is no longer "two calls" — it loops over every coin. Guess how many ordered ways make 4.

Why a sum over coins? From amount $n$ you may pay any coin $c$ first, leaving $n - c$ . Why this step? Cell C: the number of recursive children equals the number of legal coins, not a fixed 2. combine is a for-loop of additions.
Base case $C (0) = 1$ . One way to make $0$ : take no more coins. Why this step? Same "empty way = 1" logic as Ex 2 — reusing the pattern, not re-deriving it.
Fill up. $C (1) = C (0) = 1$ . $C (2) = C (1) = 1$ (only coin $1$ fits). $C (3) = C (2) + C (0) = 1 + 1 = 2$ (coins $1$ and $3$ ). $C (4) = C (3) + C (1) + C (0) = 2 + 1 + 1 = 4$ (coins $1, 3, 4$ ). Why this step? Each state reads only smaller states — always available in the cache.

Verify (by listing): ordered sums to 4: $1 + 1 + 1 + 1$ , $1 + 3$ , $3 + 1$ , $4$ = 4 sequences. ✓

Ex 4 — Grid unique paths, a tuple key (cell D)

Worked example Paths from top-left to bottom-right of a

$3 \times 4$ grid of cells (indices $r = 0..2$ , $c = 0..3$ ), moving only right or down. $P (r, c) = P (r - 1, c) + P (r, c - 1)$ , $P (0, \cdot) = P (\cdot, 0) = 1$ .

Forecast: the state now needs two numbers. Guess the count of paths to $(2, 3)$ .

Why the key must be (r,c). Two different cells can share the same $r$ but differ in $c$ ; if you cached by $r$ alone they would collide and return each other's stale answers. Why this step? Cell D — the whole lesson of 2-D DP is the key holds every variable that changes the answer.
Seed the edges. Top row and left column are all $1$ (one straight-line path along an edge). Look at the amber edge cells in the figure. Why this step? These are the base cases — the recursion bottoms out on any edge.
Fill inward (each interior cell = up + left). Reading the figure grid: row 1: $P (1, 1) = 1 + 1 = 2$ , $P (1, 2) = 2 + 1 = 3$ , $P (1, 3) = 3 + 1 = 4$ . row 2: $P (2, 1) = 2 + 1 = 3$ , $P (2, 2) = 3 + 3 = 6$ , $P (2, 3) = 6 + 4 = 10$ . Why this step? Every cell reads its up-neighbour and left-neighbour, both already computed — the memo makes each read $O (1)$ .

Verify: closed form for an $a \times b$ grid is $(a - 1 a + b - 2)$ . Here $(2 2 + 3) = (2 5) = 10$ . ✓

Ex 5 — A state that can go negative (cell E)

Worked example "Tribonacci-ish":

$T (n) = T (n - 1) + T (n - 2) + T (n - 3)$ with $T (0) = 0, T (1) = 1, T (2) = 1$ . Compute $T (5)$ , and handle the danger that $n - 3$ can be negative.

Forecast: with three look-backs, at $n = 1$ we would ask for $T (- 2)$ . Where does the code guard this?

Spot the out-of-range index. $T (1)$ would call $T (0), T (- 1), T (- 2)$ — negative arguments are meaningless. Why this step? Cell E — you must guard the base cases before recursing, or you fall off the bottom of the world.
The guard: check base cases first. if n < 3: return [0,1,1][n] intercepts $n \in {0, 1, 2}$ , so $n - 3$ is only ever evaluated when $n \geq 3$ (giving index $\geq 0$ ). Why this step? Ordering the base-case test above the recursive line is exactly what prevents the negative call — this is the "B before R" of the C-B-R-S mnemonic.
Compute. $T (3) = T (2) + T (1) + T (0) = 1 + 1 + 0 = 2$ ; $T (4) = 2 + 1 + 1 = 4$ ; $T (5) = 4 + 2 + 1 = 7$ . Why this step? Once guarded, the fill is ordinary.

Verify: sequence $0, 1, 1, 2, 4, 7$ ⇒ $T (5) = 7$ . ✓ No negative index was ever indexed. ✓

Ex 6 — Max-sum, where `combine` is `max` not `+` (cell F)

Worked example House Robber: values

$[2, 7, 9, 3, 1]$ . You may not take two adjacent houses. Maximise the sum. State: $R (i) =$ best loot using houses $i .. end$ . $R (i) = max (v_{i} + R (i + 2), R (i + 1))$ , with $R (i) = 0$ for $i \geq 5$ .

Forecast: which combining operation appears here — a sum or a choice? Guess the max loot.

Why max, not +. At each house you either rob it (take $v_{i}$ , then skip to $i + 2$ ) or skip it (move to $i + 1$ ). Only one of the two happens, so you keep the better — that is a max. Why this step? Cell F — memoization is not only for counting; combine is whatever the objective demands. Here the objective is "largest," so combine = max.
Base case beyond the array. $R (5) = R (6) = 0$ : no houses left, nothing to rob. Why this step? The degenerate "past the end" state anchors the recursion (a cousin of Ex 1's zero input).
Fill right-to-left (largest index first). $R (4) = max (1 + R (6), R (5)) = max (1, 0) = 1$ . $R (3) = max (3 + R (5), R (4)) = max (3, 1) = 3$ . $R (2) = max (9 + R (4), R (3)) = max (10, 3) = 10$ . $R (1) = max (7 + R (3), R (2)) = max (10, 10) = 10$ . $R (0) = max (2 + R (2), R (1)) = max (12, 10) = 12$ . Why this step? Each state reads only larger indices, already cached.

Verify: houses $0$ and $2$ give $2 + 9 = 11$ ; houses $0, 2, 4$ give $2 + 9 + 1 = 12$ ; that is the winner, so $R (0) = 12$ . ✓

Ex 7 — Word problem: decode-ways (cell G, real world)

Worked example A code maps

$1 \to A, \dots, 26 \to Z$ . How many ways can the digit string "226" be decoded? State: $D (i) =$ decodings of the suffix starting at index $i$ .

Forecast: "226" could split as 2 2 6, 22 6, 2 26… guess the count.

Translate English to a recurrence. At position $i$ you either take one digit (if it is $1$ – $9$ ) then solve $D (i + 1)$ , or take two digits (if they form $10$ – $26$ ) then solve $D (i + 2)$ . Add the ways. Why this step? Cell G — the skill is turning "how many decodings" into "sum over the legal first moves," the exact shape of Ex 3.
Base case. $D (len) = 1$ : reaching the end is one complete decoding (empty way = 1, same idea as Ex 2). Why this step? Fixing the base value is half the DP.
Fill from the right on "226" (indices $0, 1, 2$ , length $3$ ): $D (3) = 1$ . $D (2)$ : digit 6 valid single ⇒ $D (3) = 1$ ; no two-digit (string ends) ⇒ $D (2) = 1$ . $D (1)$ : digit 2 valid ⇒ $+ D (2) = 1$ ; two-digit 26 $\leq 26$ valid ⇒ $+ D (3) = 1$ ⇒ $D (1) = 2$ . $D (0)$ : digit 2 valid ⇒ $+ D (1) = 2$ ; two-digit 22 $\leq 26$ valid ⇒ $+ D (2) = 1$ ⇒ $D (0) = 3$ . Why this step? Each state depends only on later positions — cache-friendly.

Verify (enumerate): 2,2,6→BBF; 22,6→VF; 2,26→BZ = 3 decodings. ✓

Ex 8 — Exam twist: the stale-key bug (cell H)

Worked example A knapsack helper depends on

two things, (index, capacity), but a student caches by index only. Show, on items [(weight 1, value 6), (weight 2, value 10)] with capacity 2, why the wrong key returns a wrong number.

Forecast: the buggy code runs fast and looks correct. Guess: does it output the right answer $16$ ?

Correct recurrence. $K (i, c a p) = max (K (i + 1, c a p), value_{i} + K (i + 1, c a p - w_{i}))$ when $w_{i} \leq c a p$ ; state = $(i, c a p)$ . Why this step? Cell H is about the key, so we first name every variable that changes the answer: both $i$ and $c a p$ .
Correct answer. Take item 1 ( $w = 2, v = 10$ ) alone → 10; take item 0 only → 6; both need weight 3 > 2, impossible. Best $= 10$ . Why this step? Establish ground truth to compare against the bug.
The bug. Caching only by index: the first time $i = 1$ is solved it might be under some capacity and stored as memo[1]=v. A later call with a different remaining capacity fetches that same stale memo[1] — a value computed for the wrong capacity. Why this step? Two distinct states $(1, c a p_{a})$ and $(1, c a p_{b})$ collide onto one key, so the second silently reads the first's answer.
The fix. Key by the full tuple (i, cap). Why this step? Restores the rule "the key holds every variable that affects the result," matching Ex 4's tuple key.

Verify: correct value with tuple key = 10; the collision bug can report the max item value 10 or a stale 6 depending on call order — the point is it is not guaranteed correct. The tuple-keyed answer $10$ is checked below. ✓

Ex 9 — Limiting behaviour: counting distinct states (cell I)

Worked example For the grid of Ex 4 (

$3 \times 4$ ) and for Fibonacci $(n)$ , count distinct states, hence the time complexity.

Forecast: which grows faster as inputs scale — a 1-D DP or a 2-D DP? Guess.

1-D Fibonacci. Argument ranges over $0.. n$ ⇒ $n + 1$ distinct states, each $O (1)$ work ⇒ $O (n)$ time. Why this step? Cell I — complexity of memoization is (number of distinct states) × (work per state), nothing more.
2-D grid. States are pairs $(r, c)$ with $r \in {0, 1, 2}, c \in {0, 1, 2, 3}$ ⇒ $3 \times 4 = 12$ distinct states, each $O (1)$ ⇒ $O (r c)$ time. Why this step? The state space is the product of each dimension's range — the picture in Ex 4 literally shows all 12 cells.
Contrast with naïve recursion. Un-memoized Fibonacci makes $\approx ϕ^{n}$ calls; caching collapses that to $n + 1$ — this is exactly the DP win over plain recursion. Why this step? Shows the limiting improvement: exponential → linear.

Verify: Fibonacci $(6)$ touched exactly $7 = 6 + 1$ states (Ex 1). ✓ Grid touched $12 = 3 \times 4$ states (Ex 4). ✓

Recall One-line takeaways per cell

Base value = half the DP ::: Ex 1 vs Ex 2 have identical recurrences, different answers. k-way branch = loop of additions ::: Ex 3, Ex 7. 2-D state = tuple key ::: Ex 4; a wrong partial key silently lies, Ex 8. Guard base cases before recursing ::: Ex 5 avoids negative indices. combine is max/min for optimisation, sum for counting ::: Ex 6. Time = distinct states × work per state ::: Ex 9.

Connections

Memoization (top-down DP) — recursive + memo dict — the parent engine every example runs on
Recursion — the raw call structure before the cache
Dynamic Programming — the paradigm these examples all belong to
Tabulation (Bottom-up DP) — fill the same tables iteratively instead
Time Complexity Analysis — Ex 9's state-counting
Hash Maps / Dictionaries — the memo itself
lru_cache decorator — auto-caches by argument tuple (fixes Ex 8 for free)
Divide and Conquer — recursion without overlap, where caching would not help