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

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

Yeh page self-contained hai: yeh har symbol aur idea ko zero se build karti hai, isliye tum isse akele padh sakte ho. Jahan koi word bahar link karta hai (jaise Recursion), woh link baad mein gehraai mein jaane ki jagah hai — tumhe yeh page follow karne ke liye iska zarurat nahin hai. Ant mein tumhare paas "Memoization" topic ke liye poora mental toolkit hoga.

Recall Woh "parent topic" kya hai jiske baare mein main sunta rehta hoon?

Yeh page ek foundations companion hai ek main topic note ke saath jiska naam hai Memoization (top-down DP). Woh main note in ideas ko real problems par apply karta hai. Jo kuch bhi memoization ko samajhne ke liye chahiye woh sab yahan define hai — main note woh jagah hai jahan tum isse use karoge.

0. Ek function jo khud ko call karta hai — woh kya hota hai?

Poora topic ek idea ke upar tikaa hai: ek rule jo apne aap ke terms mein likha hota hai.

Neeche di gayi tasveer dekho. fib(5) tak pahunchne ka matlab hai pehle fib(4) aur fib(3) tak pahunchna. Woh aage split hote hain. Splitting sirf neeche rukti hai, jahan answer ke liye aur koi kaam nahin chahiye.

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

Mote double border waale red boxes woh jagah hain jahan machine splitting rok deti hai — yeh base cases hain.
★ star se marked boxes (fib3) do baar aate hain, aur ● dot se marked boxes (fib2) teen baar aate hain. Woh repetition — shape aur colour dono se flag ki gayi taaki greyscale mein bhi padhne mein aaye — woh dushman hai jise maarne ke liye poora topic banaya gaya hai.

1. Base case — jahan splitting rukti hai

2. Recurrence kya hoti hai?

Star example Fibonacci hai:

Ab us line mein har symbol decode karo:

3. Blow-up — woh dard jise hum theek kar rahe hain

Memory kyon lagaao? Kyunki plain recursion bahut zyada barbaad karti hai jab subproblems repeat hote hain.

Yeh figure call tree mein boxes count karta hai jaise $n$ badhta hai.

Common mistake "Har level par double hota hai" bilkul sahi nahin hai

Yeh sochne ka mann karta hai ki Fibonacci call tree har level par double hota hai, jo $2^{n}$ deta hai. Lekin Figure 1 mein tree dekho: fib(n) split hota hai fib(n-1) aur fib(n-2) mein — aur fib(n-2) branch chhota hai, isliye woh fib(n-1) branch se kam descendants produce karta hai. Tree lopsided hai, perfectly binary nahin.

Calls ko exactly count karne par, nodes ki sankhya $ϕ^{n}$ ki tarah badhti hai jahan $ϕ \approx 1.618$ — likha jaata hai $Θ (ϕ^{n})$ (padhte hain "theta of phi-to-the-n", matlab yeh exactly us rate par badhta hai, sirf at most nahin). Toh $2^{n}$ ek loose upper bound hai; $ϕ^{n}$ actual rate hai. Kisi bhi tarah yeh exponential hai — jo baat matter karti hai woh yeh hai: kaam multiply hota hai jaise $n$ badhta hai, aur woh catastrophic hai.

4. Cache — woh dictionary jo yaad rakhti hai

Woh "notebook" jisme recursion likhti hai woh ek dictionary hai.

5. Sab kuch jodna — memoized algorithm

Ab tumhare paas har piece hai. Yeh hai poora method, plain step-by-step pseudocode ke roop mein — woh "how" jiske liye yeh page exist karti hai. Yeh pattern hai C-B-R-S: Check, Base, Recurse, Store.

Formula Memoization template (pseudocode)

function solve(state, memo):
    # C — Check cache: kya main yeh state pehle answer kar chuka hoon?
    if state is a key in memo:
        return memo[state]          # instant O(1) reuse
 
    # B — Base case: sabse chhota input, answer seedha pata hai
    if state is a base case:
        return known_base_answer(state)
 
    # R — Recurse: yeh answer CHHOTI states se banao
    answer = combine( solve(smaller_state_1, memo),
                      solve(smaller_state_2, memo), ... )
 
    # S — Answer RETURN karne se PEHLE store karo, taaki dobara na karna pade
    memo[state] = answer
    return answer

Ise Fibonacci par trace karo taaki abstract steps concrete ban jayein:

6. Do costs — time aur memory

Ek memo speed khareedti hai, lekin woh free nahin hai — woh time bachaaने ke liye memory kharach karti hai. Dono costs ko honestly naam do.

7. Function arguments aur default values

Memoized code memo ko calls ke beech paas karta hai, isliye tumhe ek aakhri vocabulary pair chahiye.

Foundations topic ko kaise feed karti hain

Ise upar se neeche padhein — yeh upar ke sections ka exact order hai, jo dikhata hai kya kya depend karta hai:

Function (Sec. 0) raw machine hai.
Recursion (Sec. 0) ek function hai jo khud ko call karta hai; ise rukne ke liye ek base case (Sec. 1) chahiye.
Recursion jo pehle ki values ko reference karti hai woh hi ek recurrence (Sec. 2) hai.
Ek recurrence jisme repeated subproblems hain woh exponential blow-up (Sec. 3) paida karta hai — woh dard hai.
Ek dictionary (Sec. 4) jise state (Sec. 4) se key kiya gaya ho free $O (1)$ lookup (Sec. 6) deti hai.
Inhe C-B-R-S algorithm (Sec. 5) ke saath milao, memory cost (Sec. 6) aur default-argument safety (Sec. 7) ka dhyaan rakho — aur tumhare paas memoization hai.

Har arrow ka matlab hai "lower box mein upper box ki idea use hoti hai." Koi bhi path MEMOIZATION tak trace karo aur tum dobara trace kar rahe ho kyun har foundation pehle aani thi.

Equipment checklist

Daayein side cover karo aur check karo ki aage badhne se pehle har sawaal ka jawaab de sakte ho.

Kisi function ke recursive hone ka kya matlab hai?

Woh khud ko ek chhote input par call karta hai, base case ki taraf shrink karta hua.

Base case kya hai aur woh kyun zaroori hai?

Sabse chhota input jiska answer seedha pata ho; yeh STOP sign hai jo recursion khatam karta hai.

F (n) = F (n - 1) + F (n - 2)

mein

F (n)

ka kya matlab hai?

Fibonacci machine ka input

n

ke liye output — sequence mein

n

-vaan number.

Plain recursive Fibonacci exponential kyun hai, aur iska exact growth rate kya hai?

Lopsided call tree repeated subproblems ko recompute karta hai; actual node count

Θ (ϕ^{n})

ki tarah badhta hai jahan

ϕ \approx 1.618

(

2^{n}

se upar bounded).

O (1)

ka kya matlab hai?

Constant time — input size se regardless same chhoti si cost, jaise ek dictionary lookup.

Dictionary / hash map kya hota hai?

Key→value pairs ka store jisme key se near-instant lookup hoti hai.

Memoization mein state kya hai?

Current subproblem ki poori description — yeh cache key banta hai.

Memoized algorithm ke chaar steps kya hain?

C-B-R-S: Check cache → Base case → Recurse → Store (return se pehle store karo).

Memoization kaun se DO resources kharach karti hai, aur kitni?

Time

O (# states)

tak girta hai, lekin memory cache ke liye

O (# states)

aur stack ke liye

O (depth)

tak badhti hai.

def f(n, memo={}) dangerous kyun hai?

{} ek baar create hota hai aur saari calls mein share hota hai, jo invocations ke beech stale cached answers leak karta hai.

Memoization ki ek-sentence definition?

Ek aisi recursion jo har distinct subproblem ka answer ek cache mein store karti hai taaki woh exactly ek baar compute ho.

Connections

Recursion — yahan sab kuch jis engine ke upar hai
Dynamic Programming — woh umbrella jiske neeche yeh ideas rehti hain
Time Complexity Analysis — jahan se $Θ (ϕ^{n})$ aur $O (n)$ aate hain
Hash Maps / Dictionaries — cache ki data structure
Divide and Conquer — recursion bina overlap ke (memo ki zarurat nahin)
Tabulation (Bottom-up DP) — woh iterative twin jisse tum aage miloge
lru_cache decorator — Python ka built-in auto-cache