Noesis
3.7.9 · HinglishAlgorithm Paradigms

DP problems — Fibonacci, coin change (count + min), 0 - 1 knapsack

1,984 words9 min read↑ Read in English

3.7.9 · Coding › Algorithm Paradigms

1. Fibonacci — overlapping subproblems ka "hello world"

YE canonical DP example kyun hai: Naive recursion same values ko baar baar recompute karta hai.

                 F(5)
           /            \
        F(4)            F(3)      <- F(3) computed here
       /    \          /    \
    F(3)    F(2)    F(2)   F(1)   <- F(3) AGAIN, F(2) thrice...

Recursion tree mein nodes hote hain (exponential, ) lekin sirf distinct values hoti hain. Yahi gap hai jo memoization khatam kar deti hai.

KAISE — teen increasingly lean versions:

# (a) Top-down memoization
def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
 
# (b) Bottom-up table
def fib(n):
    dp = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
 
# (c) Space-optimized — we only ever need the last two
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

2. Coin Change — do flavors

Aapke paas coin denominations coins[] hain (har ek unlimited supply — yeh unbounded knapsack style hai) aur ek target amount.

2a. amount banane ke tareekon ki sankhya count karo

Yahan order kyun matter karta hai. Combinations count karne ke liye (permutations nahi) hamen coin order fix karna hoga: coins ko bahar loop karo, amount andar. Yeh ensure karta hai ki hum coin 2 ko coin 1 se pehle do alag orders mein use na karein aur double count na ho.

def count_ways(coins, amount):
    dp = [0]*(amount+1)
    dp[0] = 1                       # one way: empty set
    for c in coins:                 # coins OUTSIDE -> combinations
        for a in range(c, amount+1):
            dp[a] += dp[a-c]
    return dp[amount]

2b. amount banane ke liye coins ki minimum sankhya

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF]*amount
    for a in range(1, amount+1):
        for c in coins:
            if c <= a and dp[a-c] + 1 < dp[a]:
                dp[a] = dp[a-c] + 1
    return -1 if dp[amount] == INF else dp[amount]

3. 0/1 Knapsack — har item zyada se zyada ek baar use hoga

2D state kyun. Har item ke liye hum ek binary choice karte hain; future ko sirf itni chinta hai ki kitni capacity bachi hai aur kaun se items abhi available hain. Isliye state = (items considered, capacity used).

\underbrace{v_i + \text{dp}[i-1][w-w_i]}_{\text{take item }i,\ \text{if } w_i\le w}\big)$$ > [!intuition] Hum row $i-1$ kyun dekhte hain ($i$ nahi) > Kyunki item $i$ **zyada se zyada ek baar** use hota hai. Use lene ke baad, hamen sirf *pehle* > items ke saath aage jaana hoga — isliye hum `dp[i-1][...]` dekhte hain. (*Unbounded* knapsack mein hum `dp[i]` use karte, > reuse allow karte — woh ek index change hi poora fark hai!) ```python def knapsack(weights, values, W): n = len(weights) dp = [[0]*(W+1) for _ in range(n+1)] for i in range(1, n+1): for w in range(W+1): dp[i][w] = dp[i-1][w] # skip if weights[i-1] <= w: # can we take it? take = values[i-1] + dp[i-1][w-weights[i-1]] dp[i][w] = max(dp[i][w], take) return dp[n][W] ``` **Space optimization (1D, weight DOWNWARD iterate karo):** ```python def knapsack(weights, values, W): dp = [0]*(W+1) for i in range(len(weights)): for w in range(W, weights[i]-1, -1): # REVERSE! dp[w] = max(dp[w], values[i] + dp[w-weights[i]]) return dp[W] ``` > [!mistake] Steel-man: "1D knapsack mein weight forward loop karo" > **Kyun sahi lagta hai:** coin-change *count* mein humne amount forward loop kiya aur kaam kiya! > **0/1 ke liye kyun galat hai:** forward iteration se `dp[w-w_i]` mein pehle se item $i$ aa jaata hai, > toh item $i$ *kai baar* use hota hai → yeh **unbounded** knapsack hai, 0/1 nahi. > **Fix:** $w$ ko $W$ se **neeche** $w_i$ tak iterate karo, taaki `dp[w-w_i]` abhi bhi *pehle* > item ki value rakhe (item $i$ abhi place nahi hua). > [!example] Worked 0/1: w=[1,3,4,5], v=[1,4,5,7], W=7 > Best: items 2&3 (weights 3+4=7, value 4+5=**9**). Item 4 akela = 7. Item 1+4 = 8. > DP confirm karta hai `dp[7]=9`. *Kyun?* (i-1) reference ek item ko reuse karne se rokta hai, isliye 3+4 kisi bhi > single-item ya reused combo ko haraata hai. ![[3.7.09-DP-problems-—-Fibonacci,-coin-change-(count-+-min),-0-1-knapsack.png]] --- ## Decision cheat-sheet (80/20 core) | Problem | Loop order | Recurrence core | Base | |---|---|---|---| | Fibonacci | i: 2→n | `dp[i]=dp[i-1]+dp[i-2]` | dp[0]=0,dp[1]=1 | | Coin **count** | coin outer, amt inner ↑ | `dp[a]+=dp[a-c]` | dp[0]=1 | | Coin **min** | amt outer, coin inner | `dp[a]=min(dp[a-c]+1)` | dp[0]=0, rest ∞ | | Unbounded knap | weight inner ↑ | `dp[w]=max(dp[w], v+dp[w-wi])` | dp[..]=0 | | 0/1 knap | weight inner ↓ | `dp[w]=max(dp[w], v+dp[w-wi])` | dp[..]=0 | > [!mistake] Coin change ke liye Greedy ≠ DP > **Kyun sahi lagta hai:** "nice" coin systems (1,5,10,25) ke liye greedy optimal hai, toh log generalize karte hain. **Kyun galat hai:** coins=[1,3,4], target 6 ke liye, greedy 4+1+1=3 deta hai, DP 3+3=2 deta hai. > **Fix:** jab bhi denominations arbitrary hon, DP use karo. > [!mnemonic] **"COIN-MUD"** > **CO**mbinations → coins **O**utside. **MU**ltiple-use (unbounded) → weight up. **D**istinct/0-1 > → weight **D**own. (Aur *min* coin change amount ko bahar loop karta hai, har coin try karta hai.) > [!recall]- Feynman: ek 12-saal ke bachche ko samjhao > Socho tum seedhiyan chadh rahe ho aur har step ka jawab ek sticky note pe likh rahe ho taaki tumhe baar baar count na karna pade. > **Fibonacci**: aaj ke rabbits = kal ke + parson ke; har din ka jawab ek baar likho. > **Coin ways**: piggy bank bharne ke kitne tarike hain — ek ek coin type try karo aur tally karo. > **Coin min**: pay karne ke liye sabse kam coins — har price ke liye "price minus ek coin" dekho aur 1 jodo. > **Knapsack**: weight limit wala bag; har khilone ke liye puchho "chhodo ya lo?" aur har bachi jagah ke liye best loot yaad rakho. Answers likhna = poora trick yahi hai. --- #flashcards/coding DP use karne ke liye problem mein kya do properties honi chahiye? ::: Optimal substructure + overlapping subproblems. Naive Fibonacci recursion ki time complexity kya hai aur kyun? ::: $\Theta(\phi^n)$ kyunki $T(n)=T(n-1)+T(n-2)+1$ — same subproblems exponentially recompute hote hain. Memoized Fibonacci ki complexity kya hai? ::: $\Theta(n)$ time, har $F(k)$ ek baar compute hota hai. Coin-change COUNT mein coins ko bahar kyun loop karte hain? ::: Combinations count karne ke liye, permutations nahi — coin order fix karna double counting rokta hai. Coin-change count ka base case kya hai aur kyun? ::: dp[0]=1 — bilkul ek tarika hai (empty set) amount 0 banane ka. Coin-change MIN recurrence kya hai? ::: dp[a] = min over coins c≤a of dp[a-c]+1, dp[0]=0, rest ∞. Coin change ke liye greedy generally kyun fail hoti hai? ::: Arbitrary denominations (jaise [1,3,4], target 6) greedy todti hain: 3 coins deti hai, DP 2 deta hai. 0/1 knapsack recurrence kya hai? ::: dp[i][w]=max(dp[i-1][w], v_i+dp[i-1][w-w_i]) if w_i≤w. 0/1 knapsack row i-1 kyun dekhta hai, i nahi? ::: Har item zyada se zyada ek baar use hota hai, isliye choose karne ke baad hum sirf pehle items ke saath aage jaate hain. 1D 0/1 knapsack mein weight downward kyun iterate karte hain? ::: Taaki dp[w-w_i] mein pehle item ki value rahe, same item ko baar baar use hone se rokne ke liye (forward = unbounded hoga). 0/1 aur unbounded knapsack mein code ki ek line ka fark kya hai? ::: 0/1 weight downward iterate karta hai (i-1 reference karta hai); unbounded upward iterate karta hai (i reference karta hai, reuse allowed). ## Connections - [[Recursion and Memoization]] - [[Greedy Algorithms]] — jab greedy kaafi hai/ nahi hai - [[Time and Space Complexity]] - [[Unbounded Knapsack and Rod Cutting]] - [[Subset Sum and Partition Problems]] - [[Tabulation vs Memoization]] ## 🖼️ Concept Map ```mermaid flowchart TD DP[Dynamic Programming] OS[Optimal Substructure] OV[Overlapping Subproblems] DC[Divide and Conquer] MEMO[Memoization + Table] FIB[Fibonacci] CC[Coin Change] CNT[Count Ways] MIN[Min Coins] KNAP[0-1 Knapsack] DP -->|requires| OS DP -->|requires| OV OS -->|alone gives| DC OV -->|makes worthwhile| MEMO DP -->|implemented by| MEMO FIB -->|classic case of| OV MEMO -->|turns exponential into linear| FIB DP -->|applied to| FIB DP -->|applied to| CC DP -->|applied to| KNAP CC -->|flavor| CNT CC -->|flavor| MIN CNT -->|coins outer loop avoids| MIN KNAP -->|unbounded variant is| CC ```