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

3.7.7 · D3 · Coding › Algorithm Paradigms › Memoization (top-down DP) — recursive + memo dict

Shuru karne se pehle, vocabulary ke baare mein ek waada. Ek state ek subproblem ka poora description hota hai — argument values ka woh set jo uska answer puri tarah decide karta hai. Ek memo (ya cache) ek dictionary hoti hai jiska key woh state hoti hai aur jiska value already-computed answer hota hai. Is page pe sab kuch yahi hai: state chuno, recurrence likho, state se cache karo, return karne se pehle store karo.

Scenario matrix

Har memoization problem inhi cells mein se kisi ek mein hoti hai. Neeche ke examples mein label diya gaya hai ki woh kaun si cell cover karte hain.

#	Case class	Kya naya / tricky hai	Covered by
A	1-D state, 2-way branch	textbook shape	Ex 1
B	Base case at zero (degenerate input)	`n = 0` ka matlab kya hai?	Ex 1, Ex 2
C	1-D state, k-way branch	do fixed calls nahi, balki ek loop pe recurse karo	Ex 3
D	2-D state (tuple key)	key mein dono variables hone chahiye	Ex 4
E	Negative / out-of-range state	index karne se pehle guard lagao	Ex 5
F	Choice = max/min, not sum	`combine` hamesha `+` nahi hota	Ex 6
G	Real-world word problem	English → recurrence translate karo	Ex 7
H	Exam twist: stale-key bug	wrong key silently kyun jhooth bolta hai	Ex 8
I	Limiting behaviour / complexity	distinct states count karo	Ex 9

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

Worked example

$F (6)$ compute karo memoized recurrence $F (n) = F (n - 1) + F (n - 2)$ , $F (0) = 0$ , $F (1) = 1$ ke saath. Yeh bhi batao ki $F (0)$ ka matlab kya hai.

Forecast: padhne se pehle $F (6)$ guess karo. (Sequence: $0, 1, 1, 2, 3, 5, \dots$ )

Woh states likho jo hum touch karenge. $6$ se shuru karte hue, distinct states hain ${0, 1, 2, 3, 4, 5, 6}$ — saat ki tadaad. Yeh step kyun? Memoization ka poora speed claim yahi hai ki "ek distinct state ka ek hi computation." Pehle inhe list karne se pata chalta hai ki cache mein zyada se zyada 7 entries hongi.
Sabse chhote se fill karo (recursion yehi karta hai, bas hum order kar rahe hain apne liye). $F (2) = F (1) + F (0) = 1 + 0 = 1$ . Yeh step kyun? Base values $F (0) = 0, F (1) = 1$ diye hue hain — yeh woh sticky notes hain jinse hum shuru karte hain. Baaki sab inhi ke upar bana hai.
Oopar chadho. $F (3) = 1 + 1 = 2$ ; $F (4) = 2 + 1 = 3$ ; $F (5) = 3 + 2 = 5$ ; $F (6) = 5 + 3 = 8$ . Yeh step kyun? Har line do purani sticky notes padhti hai aur ek nayi likhti hai — exactly $O (1)$ work per state.
Degenerate input $F (0)$ ka matlab. $F (0) = 0$ : sum karne ke liye zero "1s" hain, toh empty sum $0$ hai. Base case ek definition hai, koi cheez nahi jo derive ki jaaye. Yeh step kyun? Cell B — zero input wali jagah pe beginners galat guess karte hain. Isse explicitly pakad lo.

Verify: classic sequence $0, 1, 1, 2, 3, 5, 8$ mein $F (6) = 8$ hai. ✓ Cache exactly 7 keys ke saath khatam hua ⇒ 7 computations, "distinct states" se match karta hai.

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

Worked example

$n = 5$ stairs chaddhne ke kitne tarike hain, 1 ya 2 steps leke. $W (n) = W (n - 1) + W (n - 2)$ , $W (0) = 1$ , $W (1) = 1$ .

Forecast: recurrence shape same hai Fibonacci jaisi lekin different base value hai. Kya answer $F (5) = 5$ hoga? Guess karo.

Dono base cases compare karo. Fibonacci: $F (0) = 0$ . Stairs: $W (0) = 1$ . Yeh step kyun? Cell B phir strike karta hai — recurrence akele DP fix nahi karta; base value definition ka aadha hissa hai. Ek galat number yahan se har upar wali state ko poison kar deta hai.
$W (0) = 1$ justify karo. "Zero stairs chaddhne" ke liye tum kuch nahi karte — yeh exactly ek valid (empty) tarika hai, zero nahi. Yeh step kyun? Word problem ka matlab base value decide karta hai, aur yahan "koi move nahi" bhi ek tarika hai.
Compute karo. $W (2) = W (1) + W (0) = 1 + 1 = 2$ ; $W (3) = 2 + 1 = 3$ ; $W (4) = 3 + 2 = 5$ ; $W (5) = 5 + 3 = 8$ . Yeh step kyun? Seedha cache-fill, sabse chhote se.

Verify: shifted base ke saath, stairs $n = 2..5$ ke liye $2, 3, 5, 8$ deta hai — yeh Fibonacci ek se shift hai, toh $W (5) = F (6) = 8$ . ✓ (Same engine, alag starting sticky note.)

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

Worked example Coins

${1, 3, 4}$ use karke (unlimited), $n = 4$ tak summing karne wale ordered sequences kitne hain? $C (0) = 1$ lo, aur $C (n) = \sum_{c \in {1, 3, 4}, c \leq n} C (n - c)$ .

Forecast: branch ab "do calls" nahi hai — yeh har coin pe loop karta hai. Guess karo kitne ordered ways 4 banate hain.

Coins pe sum kyun? Amount $n$ se tum koi bhi coin $c$ pehle pay kar sakte ho, $n - c$ bachta hai. Yeh step kyun? Cell C: recursive children ki tadaad legal coins ke barabar hai, fixed 2 nahi. combine additions ka ek for-loop hai.
Base case $C (0) = 1$ . $0$ banane ka ek tarika: aur coin mat lo. Yeh step kyun? Same "empty way = 1" logic jaise Ex 2 — pattern reuse kar rahe hain, re-derive nahi.
Oopar bharo. $C (1) = C (0) = 1$ . $C (2) = C (1) = 1$ (sirf coin $1$ fit hoti hai). $C (3) = C (2) + C (0) = 1 + 1 = 2$ (coins $1$ aur $3$ ). $C (4) = C (3) + C (1) + C (0) = 2 + 1 + 1 = 4$ (coins $1, 3, 4$ ). Yeh step kyun? Har state sirf chhoti states padhti hai — cache mein hamesha available.

Verify (list karke): 4 ke ordered sums: $1 + 1 + 1 + 1$ , $1 + 3$ , $3 + 1$ , $4$ = 4 sequences. ✓

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

Worked example Top-left se bottom-right tak paths ek

$3 \times 4$ grid of cells mein (indices $r = 0..2$ , $c = 0..3$ ), sirf right ya down move karte hue. $P (r, c) = P (r - 1, c) + P (r, c - 1)$ , $P (0, \cdot) = P (\cdot, 0) = 1$ .

Forecast: state ab do numbers chahti hai. $(2, 3)$ tak paths ka count guess karo.

Key (r,c) kyun honi chahiye. Do alag cells same $r$ share kar sakti hain lekin $c$ mein differ karti hain; agar sirf $r$ se cache kiya toh woh collide karenge aur ek dusre ke stale answers return karenge. Yeh step kyun? Cell D — 2-D DP ka poora lesson yahi hai ki key har woh variable hold karta hai jo answer badalta hai.
Edges seed karo. Top row aur left column sab $1$ hain (ek straight-line path ek edge ke saath). Figure mein amber edge cells dekho. Yeh step kyun? Yeh base cases hain — recursion kisi bhi edge pe bottom out karti hai.
Andar fill karo (har interior cell = up + left). Figure grid padh ke: 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$ . Yeh step kyun? Har cell apna up-neighbour aur left-neighbour padhti hai, dono already computed hain — memo har read ko $O (1)$ banata hai.

Verify: $a \times b$ grid ka closed form hai $(a - 1 a + b - 2)$ . Yahan $(2 2 + 3) = (2 5) = 10$ . ✓

Ex 5 — Ek aisi state jo negative ja sakti hai (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$ . $T (5)$ compute karo, aur yeh handle karo ki $n - 3$ negative ho sakta hai.

Forecast: teen look-backs ke saath, $n = 1$ pe hum $T (- 2)$ maangenge. Code yeh guard kahan karta hai?

Out-of-range index pakdo. $T (1)$ call karega $T (0), T (- 1), T (- 2)$ — negative arguments meaningless hain. Yeh step kyun? Cell E — tumhe base cases recurse karne se pehle guard karna hoga, warna tum duniya ke neeche se gir jaoge.
Guard: pehle base cases check karo. if n < 3: return [0,1,1][n] $n \in {0, 1, 2}$ ko intercept karta hai, toh $n - 3$ sirf tab evaluate hota hai jab $n \geq 3$ ho (index $\geq 0$ deta hai). Yeh step kyun? Base-case test ko recursive line se upar rakhna exactly wahi hai jo negative call rok ta hai — yeh C-B-R-S mnemonic ka "B before R" hai.
Compute karo. $T (3) = T (2) + T (1) + T (0) = 1 + 1 + 0 = 2$ ; $T (4) = 2 + 1 + 1 = 4$ ; $T (5) = 4 + 2 + 1 = 7$ . Yeh step kyun? Guard lag jaane ke baad, fill ordinary hai.

Verify: sequence $0, 1, 1, 2, 4, 7$ ⇒ $T (5) = 7$ . ✓ Koi negative index kabhi index nahi hua. ✓

Ex 6 — Max-sum, jahan `combine` `max` hai `+` nahi (cell F)

Worked example House Robber: values

$[2, 7, 9, 3, 1]$ . Tum do adjacent houses nahi le sakte. Sum maximize karo. State: $R (i) =$ houses $i .. end$ use karke best loot. $R (i) = max (v_{i} + R (i + 2), R (i + 1))$ , with $R (i) = 0$ for $i \geq 5$ .

Forecast: yahan kaun sa combining operation hai — sum ya choice? Max loot guess karo.

max kyun, + nahi. Har house pe tum ya toh rob karte ho ( $v_{i}$ lo, phir $i + 2$ pe skip karo) ya skip karte ho ( $i + 1$ pe jao). Dono mein se sirf ek hota hai, toh tum behtar rakhte ho — yeh ek max hai. Yeh step kyun? Cell F — memoization sirf counting ke liye nahi hai; combine wahi hota hai jo objective demand kare. Yahan objective "sabse bada" hai, toh combine = max.
Array ke baad base case. $R (5) = R (6) = 0$ : koi house nahi bacha, kuch rob karne ko nahi. Yeh step kyun? "End ke baad" wala degenerate state recursion ko anchor karta hai (Ex 1 ke zero input ka cousin).
Right-to-left fill karo (sabse bada index pehle). $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$ . Yeh step kyun? Har state sirf bade indices padhti hai, jo already cached hain.

Verify: houses $0$ aur $2$ dete hain $2 + 9 = 11$ ; houses $0, 2, 4$ dete hain $2 + 9 + 1 = 12$ ; wahi winner hai, toh $R (0) = 12$ . ✓

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

Worked example Ek code map karta hai

$1 \to A, \dots, 26 \to Z$ . Digit string "226" ko kitne tareekon se decode kiya ja sakta hai? State: $D (i) =$ index $i$ se shuru hone wale suffix ki decodings.

Forecast: "226" split ho sakta hai 2 2 6, 22 6, 2 26 ke taur pe… count guess karo.

English ko recurrence mein translate karo. Position $i$ pe tum ya toh ek digit lo (agar woh $1$ – $9$ hai) phir $D (i + 1)$ solve karo, ya do digits lo (agar woh $10$ – $26$ banta hai) phir $D (i + 2)$ solve karo. Tareekon ko add karo. Yeh step kyun? Cell G — skill yeh hai ki "kitni decodings" ko "legal first moves pe sum" mein badlo, exactly Ex 3 jaisi shape.
Base case. $D (len) = 1$ : end tak pahunchna ek poori decoding hai (empty way = 1, same idea as Ex 2). Yeh step kyun? Base value fix karna DP ka aadha kaam hai.
Right se fill karo "226" pe (indices $0, 1, 2$ , length $3$ ): $D (3) = 1$ . $D (2)$ : digit 6 valid single ⇒ $D (3) = 1$ ; koi two-digit nahi (string khatam) ⇒ $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$ . Yeh step kyun? Har state sirf baad wali positions pe depend karti hai — cache-friendly.

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

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

Worked example Ek knapsack helper

do cheezein pe depend karta hai, (index, capacity), lekin ek student sirf index se cache karta hai. Items [(weight 1, value 6), (weight 2, value 10)] aur capacity 2 pe dikhao ki wrong key galat number kyun return karta hai.

Forecast: buggy code fast run karta hai aur correct lagta hai. Guess karo: kya woh sahi answer $16$ output karta hai?

Sahi recurrence. $K (i, c a p) = max (K (i + 1, c a p), value_{i} + K (i + 1, c a p - w_{i}))$ jab $w_{i} \leq c a p$ ; state = $(i, c a p)$ . Yeh step kyun? Cell H key ke baare mein hai, toh pehle har woh variable naam karo jo answer badalta hai: $i$ aur $c a p$ dono.
Sahi answer. Item 1 lo ( $w = 2, v = 10$ ) akele → 10; sirf item 0 lo → 6; dono ko weight 3 > 2 chahiye, impossible. Best $= 10$ . Yeh step kyun? Bug se compare karne ke liye ground truth establish karo.
Bug. Sirf index se caching: pehli baar $i = 1$ solve hota hai toh kisi capacity ke neeche ho sakta hai aur memo[1]=v store ho jaata hai. Baad ki call ek alag remaining capacity ke saath wahi stale memo[1] fetch karta hai — ek value jo galat capacity ke liye compute ki gayi thi. Yeh step kyun? Do distinct states $(1, c a p_{a})$ aur $(1, c a p_{b})$ ek hi key pe collide karte hain, toh doosra silently pehle ka answer padhta hai.
Fix. Full tuple (i, cap) se key karo. Yeh step kyun? Rule restore hota hai "key har woh variable hold karta hai jo result affect karta hai," Ex 4 ke tuple key se match karta hai.

Verify: tuple key ke saath correct value = 10; collision bug 10 ya stale 6 report kar sakta hai call order ke hisaab se — baat yeh hai ki woh guaranteed correct nahi hai. Tuple-keyed answer $10$ neeche check hai. ✓

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

Worked example Ex 4 ke grid (

$3 \times 4$ ) aur Fibonacci $(n)$ ke liye, distinct states count karo, isliye time complexity bhi.

Forecast: inputs scale hone pe kaunsa zyada fast grow karta hai — 1-D DP ya 2-D DP? Guess karo.

1-D Fibonacci. Argument $0.. n$ ke range mein ⇒ $n + 1$ distinct states, har ek $O (1)$ work ⇒ $O (n)$ time. Yeh step kyun? Cell I — memoization ki complexity hai (number of distinct states) × (work per state), bas itna hi.
2-D grid. States pairs $(r, c)$ hain jahan $r \in {0, 1, 2}, c \in {0, 1, 2, 3}$ ⇒ $3 \times 4 = 12$ distinct states, har ek $O (1)$ ⇒ $O (r c)$ time. Yeh step kyun? State space har dimension ke range ka product hai — Ex 4 ki picture literally saare 12 cells dikhati hai.
Naive recursion se contrast. Un-memoized Fibonacci $\approx ϕ^{n}$ calls karta hai; caching use karne se woh $n + 1$ pe collapse ho jaata hai — yeh exactly DP ka plain recursion pe win hai. Yeh step kyun? Limiting improvement dikhata hai: exponential → linear.

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

Recall Har cell ka ek-line takeaway

Base value = DP ka aadha hissa ::: Ex 1 aur Ex 2 ke identical recurrences hain, alag answers hain. k-way branch = additions ka loop ::: Ex 3, Ex 7. 2-D state = tuple key ::: Ex 4; ek galat partial key silently jhooth bolta hai, Ex 8. Recurse karne se pehle base cases guard karo ::: Ex 5 negative indices se bachta hai. Counting ke liye combine sum hai, optimisation ke liye max/min ::: Ex 6. Time = distinct states × work per state ::: Ex 9.

Connections

Memoization (top-down DP) — recursive + memo dict — parent engine jis pe har example run karta hai
Recursion — cache se pehle raw call structure
Dynamic Programming — woh paradigm jisme yeh sab examples aate hain
Tabulation (Bottom-up DP) — same tables ko iteratively fill karo
Time Complexity Analysis — Ex 9 ka state-counting
Hash Maps / Dictionaries — memo khud
lru_cache decorator — argument tuple se auto-cache karta hai (Ex 8 free mein fix karta hai)
Divide and Conquer — recursion bina overlap ke, jahan caching help nahi karti