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

Pattern: coin-change count. Signal words: "how many distinct combinations", "order does not matter", "unlimited supply". Loop order: coins on the OUTSIDE, amount inner going up. Recurrence dp[a] += dp[a-c], base dp[0] = 1. Coins outside kyun? Agar amount bahar hota, tum 2+3 aur 3+2 ko do alag sequences count karte → permutations, combinations nahi. Coin order ko ek baar fix karna double count khatam kar deta hai.

Pattern: 0/1 knapsack. Signal: "each item usable once". Alag karne wali detail: 1D space-optimized form mein tum weight downward iterate karte ho (W → w_i). Yeh dp[w - w_i] ko pichle item ke answer ki taraf point karta rakhta hai, taaki item $i$ reuse na ho sake. Upward iterate karne se reuse ho jaata — woh unbounded knapsack hai.

Base dp[0]=0, dp[1]=1. Phir har dp[i]=dp[i-1]+dp[i-2]:

• dp[2]=1+0=1
• dp[3]=1+1=2
• dp[4]=2+1=3
• dp[5]=3+2=5
• dp[6]=5+3=8
• dp[7]=8+5=13

Full table: $[0,1,1,2,3,5,8,13]$, toh $F(7)=13$. Har step kyun? Har entry ko sirf directly neeche wali do entries chahiye — recurrence local hai, aur exactly isliye ek linear sweep kaafi hai.

Start dp=[1,0,0,0,0,0,0] (index 0..6). dp[0]=1 = empty selection.

• coin 1 (dp[a]+=dp[a-1]): $[1,1,1,1,1,1,1]$ — sirf 1s use karke har amount ke liye exactly ek way.
• coin 2 (dp[a]+=dp[a-2], $a=\mathrm{2..6}$): dp[2]+=dp[0]→2, dp[3]+=dp[1]→2, dp[4]+=dp[2]→3, dp[5]+=dp[3]→3, dp[6]+=dp[4]→4 → $[1,1,2,2,3,3,4]$.
• coin 5 (dp[a]+=dp[a-5], $a=\mathrm{5..6}$): dp[5]+=dp[0]→4, dp[6]+=dp[1]→5 → $[1,1,2,2,3,4,5]$.

Answer: 5 ways to make 6. Enumerated: 1+1+1+1+1+1, 2+1+1+1+1, 2+2+1+1, 2+2+2, 5+1. ✅

dp[0]=0, baaki $\infty$ se start. Har $a$ ke liye, dp[a]=min over c(dp[a-c]+1):

• dp[1]=dp[0]+1=1
• dp[2]=dp[1]+1=2
• dp[3]=min(dp[2]+1, dp[0]+1)=min(3,1)=1 (ek 3)
• dp[4]=min(dp[3]+1, dp[1]+1, dp[0]+1)=min(2,2,1)=1 (ek 4)
• dp[5]=min(dp[4]+1, dp[2]+1, dp[1]+1)=min(2,3,2)=2 (4+1)
• dp[6]=min(dp[5]+1, dp[3]+1, dp[2]+1)=min(3,2,3)=2 (3+3)

Answer: 2 coins ( 3+3 ). Note greedy pehle 4 pakad lega → 4+1+1 = 3 coins, worse.

Amount outer / coin inner ke saath, har dp[a] har amount par har coin par independently sum karta hai, toh yeh ordered sequences (permutations) count karta hai, combinations nahi. Trace dp=[1,0,0,0], amount a=1..3, coins c∈{1,2}:

• a=1: dp[1]+=dp[0]→1
• a=2: dp[2]+=dp[1](c=1)→1, dp[2]+=dp[0](c=2)→2
• a=3: dp[3]+=dp[2](c=1)→2, dp[3]+=dp[1](c=2)→2+1=3

Returns 3: ordered sequences 1+1+1, 1+2, 2+1. Sahi combination count sirf 2 hai (1+1+1, 1+2). Toh swap over-count karta hai — yeh ek alag problem solve karta hai.

Ek item, weight 3, value 5. dp starts $[0,0,0,0,0,0,0]$ (index 0..6). Downward ($w=6\to 3$): har dp[w]=max(dp[w], 5+dp[w-3]).

• dp[6]=max(0, 5+dp[3])=max(0,5+0)=5
• dp[5]=max(0,5+dp[2])=5
• dp[4]=max(0,5+dp[1])=5
• dp[3]=max(0,5+dp[0])=5

Har dp[w-3] jo hum read karte hain woh abhi bhi 0 hai (pre-item value) kyunki humne lower cells abhi update nahi kiye. Result: value kabhi 5 se zyada nahi — item zyada se zyada ek baar use hota hai. ✅ Agar hum upward jaate, dp[3] pehle 5 ban jaata, phir dp[6]=5+dp[3]=10 — single item ko do baar use karte (yeh unbounded behaviour hai). Direction hi poora 0/1-vs-unbounded switch hai.

2D dp[i][w] build karo with dp[i][w]=max(dp[i-1][w], v_i+dp[i-1][w-w_i]). Parent already establish karta hai dp[4][7]=9. Backtrack dp[n][W] se:

• dp[4][7]=9. Kya yeh dp[3][7] ke barabar hai? dp[3][7] (items 1,2,3, cap 7) = 4+5 = 9. Equal ⇒ item 4 (v=7,w=5) skip hua. dp[3][7] par jao.
• dp[3][7]=9 vs dp[2][7]. Items 1,2 max at cap 7 = 1+4 = 5. Equal nahi ⇒ item 3 (v=5,w=4) liya gaya. Subtract karo: dp[2][7-4]=dp[2][3] par jao.
• dp[2][3]=4 vs dp[1][3]=1. Equal nahi ⇒ item 2 (v=4,w=3) liya gaya. dp[1][3-3]=dp[1][0] par jao.
• dp[1][0]=0. Kuch nahi bacha.

Chosen items: {2, 3} (weights 3+4 = 7, values 4+5 = 9). Max value 9. ✅ Backtracking kyun kaam karta hai: agar dp[i][w]==dp[i-1][w] toh item ne kuch naya add nahi kiya, toh skip hua; warna woh extra value tha, toh liya gaya.

Yeh subset sum hai — ek 0/1 knapsack jahan "value" sirf "reachable hai ya nahi" hai. Boolean can[a]: can[0]=True; har number x ke liye, a ko downward 9 se x tak iterate karo: can[a] = can[a] or can[a-x].

• start can[0]=True, baaki False.
• x=3: can[3]=True.
• x=34: koi cell ≥34 ≤9 nahi, kuch nahi badla.
• x=4: can[7]|=can[3]→True, can[4]=True.
• x=12: too big, skip.
• x=5: can[9]|=can[4]→True, can[8]|=can[3]→True, can[5]=True.
• x=2: can[9]|=can[7] (already True), etc.

Answer: Haan, can[9]=True. Ek witness subset: 4 + 5 = 9 (ya 3 + 4 + 2 = 9). ✅

State: dp[a][k] = combinations ki sankhya jo a tak sum karti hain exactly k coins use karke, coins fixed order mein process hote hain (toh combinations, permutations nahi). Hum ${\sum }_{k=0}^{3}dp[5][k]$ chahte hain. Recurrence: coins outer loop karo, phir a, phir k: $dp[a][k]+=dp[a-c][k-1]$ Base dp[0][0]=1. Reasoning: ek coin c add karne se sum c se badhta hai aur count 1 se.

Compute karo (coins order 1 phir 2), dp[5][k] collect karo k=1,2,3 ke liye: 5 banane ke liye coins $\{1,2\}$ mein aur zyada se zyada 3 coins:

• 5 coins of 1 → 5 coins (exceeds 3, excluded).
• 2+1+1+1 → 4 coins (excluded).
• 2+2+1 → 3 coins ✅.

Sirf 1 combination ≤3 coins use karta hai. Answer: 1. Extra dimension kyun? Constraint "at most 3 coins" a akele se nahi padha ja sakta, toh yeh state mein rehna chahiye — classic sign ki tumhe ek added dimension chahiye.

• 2D: time $\Theta (nW)$ (har cell ek baar fill, $O(1)$ work each), space $\Theta (nW)$.
• 1D: time $\Theta (nW)$ (same), space $\Theta (W)$ (sirf ek weight-row rakhi jaati hai).

1D kab: tumhe sirf optimal value chahiye → 1D use karo, time asymptotically same hai aur memory kaafi kam. 2D kab: tumhe chosen items reconstruct karne hain (Ex 4.1) → tumhe poori history chahiye, toh 2D table rakho (ya parent pointers store karo). Time and Space Complexity dekho. Note $\Theta (nW)$ pseudo-polynomial hai — yeh numeric value $W$ par depend karta hai, sirf uske bit-length par nahi, toh ek bada $W$ genuinely expensive hai.

Aggregation pehchano (count = +=, optimize = max/min); combinations-vs-reuse encode karne ke liye loop order chuno; base ko trivial sawaal ke jawab ki tarah set karo; state dimension tab hi badhao jab koi constraint current cell se nahi padhi ja sakti; aur yaad rakho $\Theta (nW)$ pseudo-polynomial hai.