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

Memoization tabhi help karta hai jab subproblems overlap karein (same state ek se zyada baar maanga jaaye) aur problem mein optimal substructure ho (uska answer chhote subproblem answers se bana ho — vocabulary box dekho).

• (a) Fibonacci — YES. fib(3) ko fib(4) aur fib(5) dono request karte hain. Bahut bada overlap hai. Speedup: $O(1.618^n)\to O(n)$.
• (b) Merge sort — NO. Har split array ka ek distinct slice produce karta hai; aap kabhi same slice ko dobara sort nahi karte. Yeh Divide and Conquer hai, DP nahi. Caching aisi cheezein store karti hai jo aap kabhi dobara look up nahi karte.
• (c) Euclid gcd — NO (essentially). Har call numbers ko strictly ek chain ke along shrink karta hai — koi repeated (a,b) pair nahi aata. Yeh pehle se hi $O(\log )$ recursion hai bina kisi overlap ke.

Answer: sirf (a) ko faayda hota hai.

• A = Check cache ("kya maine yeh state dekhi hai? stored answer return karo" — ek cache hit).
• B = Base case (sabse chhote inputs jinke answers known hain, koi recursion nahi).
• C = Recurse (chhote subproblems ke answers combine karo).
• D = Store (computed answer ko cache mein return se pehle save karo).

Parent se mnemonic: C-B-R-S — Check, Base, Recurse, Store. Dhyaan do ki har letter ab ek hi line se map karta hai: R (compute) aur S (save) deliberately alag hain taaki aap store karna return se pehle kabhi na bhoolo.

Compute hone wale distinct states hain $n=2,3,4,5,6$ (values $0,1$ base case hit karti hain aur kabhi store nahi hoti). 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 karo: $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. (Dhyaan do yeh Fibonacci sequence shifted hai — kyunki yeh wahi recurrence hai alag base values ke saath.)

Figure walkthrough (s01): peach background pe rounded cells ka ek $3\times 3$ grid hai. Poori top row aur poora left column orange shaded hain aur unme se har ek mein number 1 likha hai — kyunki ek edge ke along sirf ek hi straight-line path hai (saare-right, ya saare-down). Chaar interior cells violet shaded hain; har interior number uske seedha upar wali orange/violet cell aur seedha baayein wali cell ka sum hai. Do magenta arrows bottom-right cell mein point karte hain: ek upar wali cell se neeche aata hai (value $3$) aur ek baayein se aata hai (value $3$), aur label likhta hai P(2,2)=6. Interior fill-in padhne par: $P(1,1)=1+1=2$, phir $P(1,2)=2+1=3$ aur $P(2,1)=2+1=3$, aur finally corner.

r $\mathrm{0..}m-1$ range karta hai aur c $\mathrm{0..}n-1$ range karta hai, isliye distinct states $=m\times n$. Har state $O(1)$ work karta hai (do lookups + ek add). Isliye: $\text{Time}=O(m\cdot n),\text{Space}=O(m\cdot n)\text{cache}+O(m+n)\text{recursion depth}.$ Sabse deep recursion path top-left→bottom-right diagonal hai, length $m+n$.

Distinct states count karo, calls nahi. Vocabulary se yaad karo: ek cache miss real work karta hai aur recurse karta hai; ek cache hit sirf $O(1)$ mein stored value return karta hai bina branching ke. Kisi state ki pehli baar miss hota hai (real work); har baad ki baar hit hota hai. Figure walkthrough (s02): fib(5) ke liye poora naive call tree draw kiya gaya hai — 15 circular nodes, har ek apne argument se labelled, edges ek node ko uske do children se jodti hain. Chhe magenta filled nodes wo hain jab har distinct argument ($5,4,3,2,1,0$) pehli baar reach hota hai — yeh woh cache misses hain jo real work karte hain. Saare faint violet nodes arguments ki repeat occurrences hain jo pehle se compute ho chuke hain — yeh cache hits hain aur, crucially, inhe neeche koi children nahi draw kiye gaye, kyunki hit instantly return karta hai aur kabhi expand nahi hota. Legend spell out karta hai "real work (6 distinct states)" vs "cache hit (pruned, $O(1)$)". Violet nodes ko childless leaves dekhna hi poori baat hai: exponential tree prune hokar 6 working nodes tak aa jaata hai.

Naive: maano $T(n)$ = fib(n) compute karne ke liye ki gayi total calls ki sankhya. fib(n) compute karne ke liye hum ek call karte hain (current invocation khud) plus uske do children ki saari calls. Woh "$+1$" current node hai — tree ka har node ek call count hota hai, aur yeh line hai jahan hum woh node count karte hain jis par hum khade hain: $T(n)=\underset{\text{yeh call}}{\underbrace{1}}+\underset{\text{left child}}{\underbrace{T(n-1)}}+\underset{\text{right child}}{\underbrace{T(n-2)}},T(0)=T(1)=1.$ ($n\le 1$ ke liye sirf ek single base-case call hai, isliye $T=1$.) Evaluate karte hain: $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 hain $n=0,1,2,3,4,5$ → 6 states real work karte hain (baaki cache hits hain). Yeh $O(2^n)\to O(n)$ collapse concrete numbers mein hai.

State: remaining amount t. Recurrence: t banane ke liye, har coin c ≤ t try karo, ek use karo, phir t-c optimally banao: $\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: amount 0 ke liye zero coins
    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]

T=6 ke liye compute karo: $\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 = start indices ki pair (i, j) — dono key mein hone chahiye, warna aap stale answers fetch karoge. $\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)]

"ABCBDAB" aur "BDCAB" ka ek longest common subsequence hai "BCAB" (length 4). lcs = 4.

Python memo={} ko ek baar evaluate karta hai, jab function define hota hai — har call pe nahi. Isliye wahi same dictionary object har top-level fib(...) invocation mein share hoti hai. Dono prints sahi 5 dete hain, lekin cache silently independent calls ke beech persist karta hai. Kisi competitive judge ya aisi test par jo state mutate kare (ya koi variant jahan recurrence external state pe depend kare), yeh stale cache baad ke results ko poison kar deta hai. Fix — koi bhi:

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

ya caller se ek explicit fresh dict pass karo, ya lru_cache decorator se @lru_cache use karo. fib(5) = 5 (dono baar sahi value; danger state leakage hai, yeh specific number nahi).

Index i par answer dono i aur remaining capacity cap par depend karta hai. Do alag capacities same i reach karke alag answers produce karti hain, lekin sirf i se cache karne par woh collide kar jaati hain — pehle stored wali baad ki saari cap values ke liye return ho jaati hai. Yeh fast run karta hai aur sahi lagta hai, yahi exactly isse dangerous banata hai. Rule: memo key mein har woh variable hona chahiye jo answer badalta ho. Fix:

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

Bottom-up ek table ko base cases se upward fill karta hai — koi recursion nahi, isliye koi stack-overflow risk nahi:

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]

n=7 ke liye table: [1,1,2,3,5,8,13,21] → ways(7) = 21, memoized answer se identical. Same recurrence, same complexity $O(n)$, alag control flow.

Poore page ka ek-line summary ::: Honest recurrence likho, cache ko poore state se key karo, return se pehle store karo, aur fresh dict pass karo — phir distinct states count karke cost karo.