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

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

Hum sab kuch ek chhote se example ke around banate hain: $F(5)$ compute karna, yaani 5th Fibonacci number. Itna chhota ki poora call tree draw kar sako, itna bada ki waste dikhaye.

---

Step 1 — "Recurrence" kya hoti hai? (woh rule jo bade se chhota banata hai)

KYA. Recurrence ek rule hai jo kehta hai: "bade input ka answer chhote inputs ke answers se banta hai." Fibonacci ke liye rule yeh hai:

$\underset{\text{answer we want}}{\underbrace{F(n)}}=\underset{\text{answer for input one smaller}}{\underbrace{F(n-1)}}+\underset{\text{answer for input two smaller}}{\underbrace{F(n-2)}}$

do starting facts ke saath jo humein simply bataye gaye hain (inke liye koi rule nahi chahiye):

$\underset{\text{base fact}}{\underbrace{F(0)=0}},\underset{\text{base fact}}{\underbrace{F(1)=1}}$

KYUN. Yahan har symbol earn kiya hua hai: $F$ sirf ek naam hai "us function ke liye jo ek number $n$ leta hai aur $n$-th Fibonacci value return karta hai." Chhote $(n-1)$ aur $(n-2)$ chhote inputs hain, isliye rule hamesha do base facts ki taraf neeche ki taraf point karta hai. Agar yeh do base facts na hon toh rule hamesha chhote se chhote inputs maangta rehta — jaise koi seediyon wali staircase jiska koi bottom step hi na ho.

PICTURE. Neeche, bada node woh hai jo hum chahte hain; do arrows do chhoti cheezein dikhate hain jinki use zaroorat hai. Woh single fork, repeat hote hote, hi poora algorithm hai.

---

Step 2 — Rule ko poora unfold karo: $F(5)$ ka naive call tree

KYA. Step 1 ka rule baar baar apply karo. $F(5)$ ko $F(4)$ aur $F(3)$ chahiye. Unhe bhi apne do-do children chahiye, aur yeh silsila tab tak chalta hai jab tak har branch base fact $F(0)$ ya $F(1)$ pe khatam na ho jaaye.

KYUN. Hum optimize karne se pehle unfold karte hain kyunki jo waste tune draw nahi kiya, woh dikh nahi sakta. Yeh tree exactly wahi hai jo ek plain recursive function karta hai — har node ek function call hai, har leaf ek base case hai jo turant return karta hai.

PICTURE. Poora tree. Nodes gino: 15 hain. Dekho ki tree ka bottom kitna fata hua hai — woh motapan hi dushman hai.

---

Step 3 — Repeats dhoondo: wahi subproblem, baar baar

KYA. Step 2 ke tree mein chalo aur har node ko uski input value ke hisaab se colour karo. Count karo ki har distinct input kitni baar appear hota hai:

input $n$	naive tree mein kitni baar compute hua
$F(4)$	1
$F(3)$	2
$F(2)$	3
$F(1)$	5
$F(0)$	3

KYUN. Yeh table caching ka poora justification hai. $F(2)$ 3 alag baar maanga jaata hai, aur uska answer hamesha $1$ hota hai. Ise recompute karna bilkul wasteful hai — jaise $1+1$ teen baar scratch se jodte raho. Jitna aage jaoge, utna bura hoga: $F(n)$ ke liye nodes ki count ${\varphi }^n$ ki tarah badhti hai, jahan

$\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618(\text{the golden ratio}).$

PICTURE. Wahi tree, ab colour-coded. Ek hi colour share karne wala har node identical subproblem hai. Tumhari aankh turant duplication dekh leti hai.

Recall

$F(3)$ ko do baar recompute karna pointless kyun hai? ::: Uska answer ($2$) kabhi nahi badlega — woh sirf uski input pe depend karta hai, isliye doosra computation pehle jaisa hi result dega.

---

Step 4 — Memo introduce karo: ek sticky-note notebook

KYA. Ek dictionary banao — ise $\text{memo}$ bulao — jo ek input ko uske already-computed answer se map kare:

$\text{memo}[n]=\text{the value of }F(n),\text{once we know it}.$

Hum har call ke upar ek naya rule add karte hain: koi bhi kaam karne se pehle, poocho "kya $n$ already $\text{memo}$ mein ek key hai?" Agar haan, toh $\text{memo}[n]$ turant return karo aur ruko.

KYUN. Dictionary (dekho Hash Maps / Dictionaries) humein $O(1)$ lookup deta hai — ek already-known answer padhna flat, tiny time leta hai chahe $n$ kitna bhi bada ho. Isliye hash map, na ki, kaho, list scan: hum chahte hain "kya maine yeh exact state dekha hai?" ek step mein answer ho. Yeh repeated-work problem ko look-it-up problem mein badal deta hai.

PICTURE. Notebook computation ke saath saath left-to-right bharta jaata hai. Grey cells abhi bhi empty hain (unknown); bhari hui cells woh answers hain jinhe hum kabhi recompute nahi karenge.

---

Step 5 — Tree prune karo: memo actually kya kaata hai

KYA. $F(5)$ dobara run karo, lekin ab pehli baar koi subproblem finish hone pe hum use store karte hain, aur baad ki har request notebook se answer hoti hai — uska poora subtree kabhi draw hi nahi hota.

KYUN. Recursion ka order depth-first hota hai (pehle leftmost branch bilkul neeche tak). Isliye $F(3)$, $F(2)$, $F(1)$, $F(0)$ sab tree ke left side se neeche jaate waqt compute aur store ho jaate hain. Jab right side baad mein $F(3)$ maangti hai, woh turant cache hit karti hai — woh poora right subtree, jisme 5 nodes the, ek single lookup mein collapse ho jaata hai.

PICTURE. Pruned tree: solid nodes ek baar compute hote hain; grayed-out, crossed subtrees woh hain jo cache ne skip kar diye. Step 2 ke mote tree se surviving nodes compare karo.

---

Step 6 — Jo bacha use gino: exponential-to-linear collapse

KYA. Pruning ke baad, kitne nodes actually real kaam karte hain? Exactly ek per distinct input: $F(0),F(1),F(2),F(3),F(4),F(5)$ — yeh hai $n+1=6$ nodes. Original tree ka har doosra node ek cache hit ban gaya.

KYUN. Yeh poore paradigm ka punchline hai, aur yeh sirf arithmetic hai:

$\text{total time}=\underset{n+1}{\underbrace{(\text{number of distinct states})}}\times \underset{O(1)}{\underbrace{(\text{work per state})}}=O(n).$

Do growth curves compare karo. Naive count ${\varphi }^n$ follow karta hai (roughly har step pe double); memoized count straight line $n+1$ follow karta hai. $n=5$ ke liye yeh $15$ vs $6$ hai; $n=40$ ke liye yeh roughly 330 million vs 41 hai. (Dekho Time Complexity Analysis — hum distinct states count karte hain, raw calls nahi.)

PICTURE. Ek chalkboard pe do curves: runaway exponential vs tame straight line.

---

Step 7 — Degenerate cases (reader ko kabhi untested input pe mat fasao)

KYA & KYUN & PICTURE, ek ek case ke liye:

Case $n=0$ aur $n=1$ (pure base facts). Step 1 ka rule kabhi apply nahi hota; base line turant return karti hai. Tree ek single node hai — koi fork hi nahi. Agar tum inhe bhool jaao, toh recursion $F(-1)$, $F(-2)$, ... ke liye forever maangti rehti.

Case: cache check missing (the "no notebook" bug). Agar tum $\text{C}$heck line delete kar do, tum wapas Step 2 ka mota tree pe aa jaate ho — sahi answer, exponential time. Code dekhne mein theek lagta hai aur chhote inputs pe sahi results deta hai, yahi is bug ko sneaky banata hai.

Case: store bhool gaye (the "empty notebook" bug). Agar tum recurse karo lekin kabhi $\text{memo}[n]=\dots$ na likho, toh check hamesha miss karta hai kyunki kuch store hi nahi hua. Wahi mota tree, wahi waste. Return karne se pehle store karo.

---

Ek-picture summary

Left: mota naive tree (15 nodes, waste colour mein). Right: pruned memoized run (6 real nodes + notebook ko arrows). Bottom: do growth curves. Ek nazar mein poori derivation samajh aati hai.

Recall Feynman retelling — poora walkthrough seedhe shabdon mein

Hum 5th Fibonacci number chahte the. "Bada matlab do chhote" wala rule (Step 1) chhote calls ki ek bhari-puri tree mein unfold hota hai (Step 2). Jab humne woh tree colour ki toh hum use rang-e-haath pakad liya: wahi chhote sums baar baar aate hain — $F(2)$ teen baar, $F(1)$ paanch baar (Step 3). Toh humne ek notebook pakdi, yani memo dict, aur ek waada kiya: jab bhi koi chhota sum finish karo toh answer likh lo, aur koi sum karne se pehle pehle notebook mein jhaanko (Step 4). Ab jab tree ka right half kuch maangta hai jo left half pehle hi solve kar chuka hai, hum sirf note padhte hain — poori branch gayab ho jaati hai (Step 5). Sirf woh sums ginne pe jo humne sach mein kiye, har distinct number ke liye ek hai: paandreh ki jagah chheh, aur bade inputs ke liye millions-vs-dozens (Step 6). Finally humne pakka kiya ki kuch kaat na khaaye: do base facts ka girna rokna, aur do classic bugs — jhaankna bhoolna, ya likhna bhoolna — dono chupke se tumhe woh slow moti tree wapas de dete hain (Step 7). Yahi hai memoization: woh recursion jo yaad rakhti hai.

Connections

• Recursion — har step ka tree hi recursion hai; memoization sirf notebook add karta hai
• Dynamic Programming — yeh collapse iss paradigm ka dil hai
• Tabulation (Bottom-up DP) — wahi notebook bharta hai, lekin pehle bottom row, koi tree nahi
• Time Complexity Analysis — Step 6 hai "distinct states × work per state"
• Divide and Conquer — recursion bina Step 3 ke coloured repeats ke
• Hash Maps / Dictionaries — Step 4 ka $O(1)$ notebook
• lru_cache decorator — Python ka built-in memo, Step 7 mein fix