Exercises — Memoization (top-down DP) — recursive + memo dict

Memoization only helps when subproblems overlap (the same state is asked more than once) and the problem has optimal substructure (its answer is built from smaller subproblem answers — see the vocabulary box).

• (a) Fibonacci — YES. fib(3) is requested by both fib(4) and fib(5). Massive overlap. Speedup: $O(1.618^n)\to O(n)$.
• (b) Merge sort — NO. Each split produces a distinct slice of the array; you never sort the same slice twice. This is Divide and Conquer, not DP. Caching stores things you never look up again.
• (c) Euclid gcd — NO (essentially). Each call strictly shrinks the numbers along a single chain — no repeated (a,b) pair arises. It's already $O(\log )$ recursion with no overlap.

Answer: only (a) benefits.

• A = Check the cache ("have I seen this state? return the stored answer" — a cache hit).
• B = Base case (smallest inputs with a known answer, no recursion).
• C = Recurse (combine the answers of the smaller subproblems).
• D = Store (save the computed answer into the cache before returning).

Mnemonic from the parent: C-B-R-S — Check, Base, Recurse, Store. Notice each letter now maps to exactly one line: the R (compute) and the S (save) are deliberately split so you never forget to store before returning.

Distinct states computed are $n=2,3,4,5,6$ (the values $0,1$ hit the base case and are never stored). Fibonacci sequence: $F(0)=0,F(1)=1,F(2)=1,F(3)=2,F(4)=3,F(5)=5,F(6)=8$. $\text{memo}=\{2:1,3:2,4:3,5:5,6:8\}$ fib(6) = 8.

Build up: $W(0)=1,W(1)=1,W(2)=2,W(3)=3,W(4)=5,W(5)=8,W(6)=13,W(7)=21$. ways(7) = 21. (Notice it's the Fibonacci sequence shifted — because it's the same recurrence with different base values.)

Figure walkthrough (s01): a $3\times 3$ grid of rounded cells sits on the peach background. The whole top row and the whole left column are shaded orange and every one of them holds the number 1 — because along an edge there is only a single straight-line path (all-right, or all-down). The four interior cells are shaded violet; each interior number is the sum of the orange/violet cell directly above it and the one directly to its left. Two magenta arrows point into the bottom-right cell: one coming down from the cell above (value $3$) and one coming from the left (value $3$), and the label reads P(2,2)=6. Reading the interior fill-in: $P(1,1)=1+1=2$, then $P(1,2)=2+1=3$ and $P(2,1)=2+1=3$, and finally the corner.

r ranges over $\mathrm{0..}m-1$ and c over $\mathrm{0..}n-1$, so distinct states $=m\times n$. Each state does $O(1)$ work (two lookups + one add). Therefore: $\text{Time}=O(m\cdot n),\text{Space}=O(m\cdot n)\text{cache}+O(m+n)\text{recursion depth}.$ The deepest recursion path is the top-left→bottom-right diagonal, length $m+n$.

Count distinct states, not calls. Recall from the vocabulary: a cache miss does real work and recurses; a cache hit just returns the stored value in $O(1)$ without branching. The first time a state is reached it is a miss (real work); every later time it is a hit. Figure walkthrough (s02): the full naive call tree for fib(5) is drawn — 15 circular nodes, each labelled with its argument, edges linking a node to its two children. The six magenta filled nodes are the first time each distinct argument ($5,4,3,2,1,0$) is reached — these are the cache misses that do real work. All the faint violet nodes are repeat occurrences of arguments already computed — these are cache hits and, crucially, they are drawn with no children below them, because a hit returns instantly and never expands. The legend spells out "real work (6 distinct states)" vs "cache hit (pruned, $O(1)$)". Seeing the violet nodes as childless leaves is the whole point: the exponential tree is pruned down to 6 working nodes.

Naive: let $T(n)$ = the total number of calls made to compute fib(n). To compute fib(n) we make one call (the current invocation itself) plus all the calls its two children make. That "$+1$" is the current node — every node in the tree counts as one call, and this line is where we count the node we are standing on: $T(n)=\underset{\text{this call}}{\underbrace{1}}+\underset{\text{left child}}{\underbrace{T(n-1)}}+\underset{\text{right child}}{\underbrace{T(n-2)}},T(0)=T(1)=1.$ (For $n\le 1$ there is just the single base-case call, so $T=1$.) Evaluating: $T(2)=1+1+1=3,T(3)=1+3+1=5,T(4)=1+5+3=9,T(5)=1+9+5=15$. 15 total calls. Memoized: cache-miss states are $n=0,1,2,3,4,5$ → 6 states do real work (the rest are cache hits). This is the $O(2^n)\to O(n)$ collapse in concrete numbers.

State: the remaining amount t. Recurrence: to make t, try each coin c ≤ t, use one of it, then make t-c optimally: $\text{MC}(t)=1+{\min }_{c\le t}\text{MC}(t-c),\text{MC}(0)=0.$

def min_coins(t, coins, memo=None):
    if memo is None: memo = {}
    if t in memo: return memo[t]
    if t == 0: return 0                # base: zero coins for amount 0
    best = float('inf')
    for c in coins:
        if c <= t:
            best = min(best, 1 + min_coins(t - c, coins, memo))
    memo[t] = best
    return memo[t]

Compute for T=6: $\text{MC}(0)=0$, $\text{MC}(1)=1$, $\text{MC}(2)=2$, $\text{MC}(3)=1$, $\text{MC}(4)=1$, $\text{MC}(5)=2$ (=4+1), $\text{MC}(6)=2$ (=3+3). min_coins(6) = 2.

State = the pair of start indices (i, j) — both must be in the key, or you fetch stale answers. $\text{LCS}(i,j)=\{\begin{array}{ll}0& i=|A|\text{ or }j=|B|\\ 1+\text{LCS}(i+1,j+1)& A_i=B_j\\ \max (\text{LCS}(i+1,j),\text{LCS}(i,j+1))& A_i\ne B_j\end{array}$

def lcs(i, j, A, B, memo=None):
    if memo is None: memo = {}
    if (i, j) in memo: return memo[(i, j)]
    if i == len(A) or j == len(B): return 0
    if A[i] == B[j]:
        ans = 1 + lcs(i+1, j+1, A, B, memo)
    else:
        ans = max(lcs(i+1, j, A, B, memo), lcs(i, j+1, A, B, memo))
    memo[(i, j)] = ans
    return memo[(i, j)]

For "ABCBDAB" and "BDCAB" a longest common subsequence is "BCAB" (length 4). lcs = 4.

Python evaluates memo={} once, when the function is defined — not per call. So the same dictionary object is shared across every top-level fib(...) invocation. Both prints give the correct 5, but the cache silently persists between independent calls. On a competitive judge or a test that mutates state (or a variant where the recurrence depends on external state), this stale cache poisons later results. Fix — any of:

def fib(n, memo=None):
    if memo is None: memo = {}
    ...

or pass an explicit fresh dict from the caller, or use @lru_cache from lru_cache decorator. fib(5) = 5 (correct value both times; the danger is state leakage, not this specific number).

The answer at index i depends on both i and the remaining capacity cap. Two different capacities reaching the same i produce different answers, but caching by i alone makes them collide — the first one stored is returned for all later cap values. It runs fast and looks right, which is exactly why it's dangerous. Rule: the memo key must include every variable that changes the answer. Fix:

if (i, cap) in memo: return memo[(i, cap)]
...
memo[(i, cap)] = max(skip, take)
return memo[(i, cap)]

Bottom-up fills a table from the base cases upward — no recursion, so no stack-overflow risk:

def ways(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Table for n=7: [1,1,2,3,5,8,13,21] → ways(7) = 21, identical to the memoized answer. Same recurrence, same complexity $O(n)$, different control flow.

One-line summary of the whole page ::: Write the honest recurrence, key the cache by the full state, store before returning, and pass a fresh dict — then cost it by counting distinct states.