Noesis
3.7.7 · D5 · HinglishAlgorithm Paradigms

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

2,424 words11 min read↑ Read in English

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

Do recursion trees — har answer ke peeche ka intuition

True or false — justify karo

Memoization hamesha plain recursion se better hota hai.
False — yeh tabhi help karta hai jab subproblems overlap karein (ek node recursion tree mein do baar aaye). Merge sort mein halves hamesha distinct hoti hain, toh cache ko kabhi hit nahi milti aur tum memory waste karte ho. Yeh Divide and Conquer hai, DP (Dynamic Programming) nahi.
Memoization uss answer ko change kar deta hai jo recursion compute karta hai.
False — yeh sirf speed change karta hai. Cached value bilkul wohi hai jo recursion recompute karta; tum recomputation ko stored lookup se trade kar rahe ho, correctness ko kabhi nahi.
Top-down aur bottom-up DP ki time complexity alag hoti hai.
False — same recurrence, same number of distinct states, same work per state, isliye same big-O. Yeh sirf control flow (recursion vs iteration) aur kaun se states touch hote hain, mein differ karte hain.
Memoization stack overflow ka risk remove kar deta hai.
False — yeh redundant calls remove karta hai, lekin recursion phir bhi ek baar base case tak descend karti hai, isliye depth ho sakti hai. Python mein default recursion limit sirf lagbhag 1000 frames hai, isliye ek deep chain (jaise fib(100000) bina help ke) Recursion stack blow kar deta hai even when fully memoized — neeche edge-case note dekho.
Cache add karne se koi bhi exponential algorithm polynomial ho jaata hai.
False — tabhi, jab distinct states ki sankhya polynomial ho. Agar state khud exponential hai (jaise items ka subset → states), toh cache exponentially large hai aur tum asymptotically kuch nahi gain karte.
@lru_cache functionally ek manual memo dict ke equivalent hai.
Mostly true, with caveats — [[lru_cache decorator|lru_cache]] ko hashable arguments chahiye aur jab maxsize set ho toh entries evict ho sakti hain. Ek hand-rolled dict kabhi evict nahi karta, isliye results tabhi differ karte hain agar tum eviction par rely karo ya unhashable state pass karo.
Agar kisi function mein optimal substructure hai toh woh automatically memoizable hai.
False — tumhe optimal substructure aur overlapping subproblems dono chahiye. Optimal substructure akele (distinct subproblems ke saath) sirf divide-and-conquer hai; cache koi kaam nahi karta.
Memo dict ko kaam karne ke liye global hona zaroori hai.
False — yeh ek parameter, closure variable, ya decorator ka hidden store ho sakta hai. Jo matter karta hai woh yeh hai ki same cache ek top-level invocation ke recursive calls ke beech share ho.

Error dhundho

def fib(n, memo={}): ... — kya galat hai?
Default {} function-definition time par ek baar create hota hai aur har alag top-level call ke beech share hota hai, isliye state alag-alag invocations ke beech leak hoti hai. Fix: memo=None phir if memo is None: memo = {}.
Ek knapsack solver sirf index se cache karta hai jabki recurrence (index, capacity) par depend karta hai. Kya toot jaata hai?
Same index lekin alag capacity wale do calls collide karte hain: doosra pehle wala stale answer padhta hai. Key mein har variable hona chahiye jo result change kare — yahan tuple (index, capacity).
def f(n, memo=None):
    if memo is None: memo = {}
    if n < 2: return n
    return f(n-1, memo) + f(n-2, memo)
Yeh phir bhi exponential kyun hai?
Ek base case hai aur memo pass ho raha hai, lekin kuch kabhi store nahi hota aur koi cache check nahi hai. Read-and-write steps ke bina dict dead weight hai — yeh hamesha khali rahti hai.
if n < 2: return n
if n in memo: return memo[n]
Base case cache se pehle check hota hai. Kya yeh ek bug hai?
Chhote base cases ke liye correctness bug nahi hai, lekin unke liye wasteful hai aur ek smell hai: convention hai cache-check pehle (C-B-R-S mein C: Check → Base → Recurse → Store). Asli danger tab hai agar base cases expensive hote — tum unhe cache karne ki bajay har baar recompute karte.

Store-before-return: sahi pattern ko pitfall se compare karo.

# WRONG — value kabhi save nahi hoti: 'return' fire hota hai, store line unreachable hai
def f(n, memo):
    ...
    return f(n-1, memo) + f(n-2, memo)
    memo[n] = ...          # dead code, kabhi nahi chalta
 
# RIGHT — compute karo, STORE karo, phir stored value return karo
def f(n, memo):
    ...
    memo[n] = f(n-1, memo) + f(n-2, memo)   # S: pehle store karo
    return memo[n]                          # phir wapas do

::: WRONG version mein return immediately exit kar jaata hai, isliye uske neeche wala assignment unreachable hai aur cache khali rehti hai — phir se exponential behaviour milta hai. Hamesha memo mein Store karo return se pehle (C-B-R-S mein S).

Ek recursion memo[n] = f(n-1) + f(n-2) store karta hai aur phir return f(n) top call ko recompute karta hai. Problem?
Tum value store karte ho lekin phir ise return karne ke liye ek fresh recursion trigger karte ho memo[n] return karne ki bajay. Stored value directly return karo — warna tum poora subtree ek baar aur re-run kar lete ho.
Koi time.time() par depend karne wale function ko cache karta hai. Ise memoize karna galat kyun hai?
Woh function pure nahi hai — uska output hidden external state par depend karta hai jo key mein nahi hai. Memoization assume karta hai "same inputs → same output"; jab yeh toote, cached values silently galat ho jaati hain.
Ek grid solver cache ko r * COLS + c se key karta hai. Koi risk?
Theek hai agar COLS fixed hai aur c < COLS hamesha — yeh ek valid injective flattening hai. Yeh tab toot jaata hai jab c equal ya exceed kar sake COLS, kyunki tab do alag (r,c) pairs same integer par map karte hain aur collide karte hain.

Why questions

Hum time complexity ke liye function calls ki jagah distinct states kyun count karte hain?
Kyunki pehli computation ke baad har repeated call ek (constant-time) dict lookup hai. Total time = (unique states ki sankhya) × (work per state), jo actually compute hota hai. Time Complexity Analysis dekho.
Hume return karne se pehle cache mein store kyun karna chahiye, baad mein nahi?
return ke baad ki line unreachable dead code hai, isliye "return then store" kabhi actually store nahi karta. Safe pattern hai compute karo → memo[state] = ans → return memo[state], taaki value ek hi raaste par save ho. (Upar WRONG/RIGHT snippet dekho.)
Memoization sirf woh states compute kyun karta hai jo tumhe "actually chahiye," tabulation ki tarah nahi?
Recursion lazy hai: woh goal se descend karta hai aur sirf un subproblems ko visit karta hai jo usse reachable hain. Tabulation (Bottom-up DP) poori table fill karta hai, possibly un states ko bhi jis par answer kabhi depend nahi karta.
Base case value ko sahi paana "sabse error-prone part" kyun kaha jaata hai?
Har answer ultimately base cases se assemble hota hai. Ek galat base value (jaise W(0)=0 ki jagah 1) upar propagate hoti hai aur har result corrupt kar deti hai — recurrence sahi hai lekin foundation sada hua hai.
Cache key mein har parameter kyun hona chahiye jo answer affect kare?
Key ek subproblem ki identity hai. Agar do genuinely alag subproblems ek key share karein, doosra silently pehle ka answer padhta hai. Ek variable miss karna = false cache hits = galat output jo phir bhi fast run karta hai.
Cache add karne ke baad bhi Python ki recursion depth kyun kam nahi hoti?
Cache repeat calls (breadth) remove karta hai, lekin base case tak jaane wali sabse deep single chain frame by frame stack hoti rehti hai, aur Python koi tail-call optimization nahi karta — woh kabhi tail recursive call ke liye ek frame reuse nahi karta. Isliye depth rehti hai aur ~1000-frame limit hit ho sakti hai.
Memoization DP ka ek form kyun maana jaata hai, sirf ek optimization trick nahi?
Kyunki isko do DP properties chahiye — optimal substructure aur overlapping subproblems — aur yeh systematically subproblem answers reuse karta hai. Yeh Dynamic Programming ka top-down implementation hai, tabulation ka twin.

Edge cases

Fibonacci mein n = 0 ya n = 1 hone par cache kya karta hai?
Kuch nahi — woh base case hit karte hain aur kisi bhi store se pehle immediately return karte hain, isliye sabse chhote inputs kabhi cache nahi hote. Sirf memoize hote hain. Yeh sahi aur intentional hai.
Grid Unique Paths mein, poori pehli row aur pehla column base case return 1 kyun hai?
Ek edge ke along (r == 0 ya c == 0) exactly ek straight-line path hai — tum sirf ek hi legal direction mein ja sakte ho. Branching nahi matlab ek path, isliye recursion wahan rokni chahiye.
Agar tum ek memoized function ko base case se neeche input par call karo, jaise fib(-3)?
if n < 2: return n ke saath yeh -3 return karta hai — garbage, kyunki recurrence kabhi negatives ke liye define nahi hua tha. Memoization faithfully nonsense cache karta hai; tumhe khud domain guard karna hoga.
Python mein fib(100000) perfect cache ke saath bhi — actually kya hota hai, aur kaise fix karein?
Yeh RecursionError raise karta hai kyunki sabse deep chain Python ki default limit of ~1000 frames exceed karti hai — cache time help karta hai, depth nahi. Fixes: ise sys.setrecursionlimit(...) se raise karo, ek iterative bottom-up loop mein convert karo (koi stack nahi), ya explicit stack use karo. Isme lean karne ke liye koi tail-call optimization nahi hai.
Agar recursion mein koi repeated subproblems nahi hain (sab states distinct hain), toh cache kya achieve karta hai?
Har lookup miss hoti hai, isliye tum poora recursion cost plus memory aur hashing overhead of the dict pay karte ho. Net effect: same time, worse constants. Yeh woh divide-and-conquer case hai jahan memo hurt karta hai.
Memoized recursion ki space cost kya hai, aur do terms kyun?
Cache ke liye plus live call stack ke liye . Caching ke baad bhi, pending calls ki sabse deep chain simultaneously stack frames occupy karti hai — aur tail-call optimization ke bina woh depth reduce nahi hoti.
Recall Ek-line self-test

Agar tum kisi bhi DP problem ke liye "full state kya hai, aur ek galat base value uske upar wale poore tree ko kya karta hai" answer kar sako, toh tumne is page ko internalize kar liya.

Connections