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

3.7.9 · D3 · Coding › Algorithm Paradigms › DP problems — Fibonacci, coin change (count + min), 0 - 1 kn

Scenario matrix

Examples karne se pehle, chalte hain har alag situation list karte hain jo ye char DP problems de sakti hain. Har row ek "case class" hai; last column us example ka naam batata hai jo use cover karta hai.

#	Case class	Kya special hai / beginners kahan toot jaate hain	Cover hota hai
A	Fibonacci, ordinary $n$	base se upar build karo — "sticky note" walk	Ex 1
B	Fibonacci, degenerate $n = 0, 1$	recursion recurrence se pehle rukni chahiye	Ex 1
C	Coin count, reachable target	`dp[a]+=dp[a-c]`, coins bahar	Ex 2
D	Coin count, target $= 0$	"empty set" ka answer = 1, 0 nahi	Ex 2
E	Coin min, greedy fail ho jaata	DP ko greedy ko beat karna hai	Ex 3
F	Coin min, impossible target	answer $- 1$ hona chahiye, koi galat number nahi	Ex 4
G	0/1 knapsack, ordinary	2D table, row $i - 1$ ki taraf wapas dekho	Ex 5
H	0/1 knapsack, capacity 0 / item bahut bhaari	degenerate, kuch fit nahi hota	Ex 6
I	0/1 knapsack, 1D reverse-loop correctness	direction trap concrete roop mein	Ex 7
J	Word problem (real world)	ek story ko weights/values mein translate karo	Ex 8
K	Exam twist — count vs permutations	loop-order meaning badal deta hai	Ex 9

Ab hum har interesting cell ka ek example dekhenge. Pehle Forecast padho aur sach mein andaza lagao — seekhna us gap mein hota hai jo tumhare andaze aur sach ke beech hota hai.

Ex 1 — Fibonacci, ordinary + degenerate (cells A, B)

Worked example

$F (7)$ compute karo, aur alag se $F (0)$ aur $F (1)$ . Forecast: aage padhne se pehle likh lo tumhare hisaab se $F (7)$ kya hai. (Sequence: $0, 1, 1, 2, 3, 5, 8, 13, \dots$ )

Step 1 — Pehle degenerate base handle karo. $F (0) = 0$ , $F (1) = 1$ . Ye diye gaye hain, compute nahi kiye. Yeh step kyun? Recurrence $F (n) = F (n - 1) + F (n - 2)$ ko do pehle ki values chahiye; $n = 0$ ya $n = 1$ ke liye do pehle ki values hoti hi nahi, isliye formula wahan undefined hai. Base cases woh floor hai jis par recursion khada hota hai — cell B bilkul yehi hai "formula jaldi mat lagao."

Step 2 — Table ko upar roll karo (space-optimized, sirf last two rakho). Figure dekho: har naya bar apne peechhe ke dono bars ka sum hai.

$i$	0	1	2	3	4	5	6	7
$F$	0	1	1	2	3	5	8	13

Yeh step kyun? Har entry sirf apne seedha neeche ke dono entries use karti hai — recurrence local hai, aur isliye $Θ (n)$ time aur $O (1)$ memory kaafi hai.

Verify karo: $F (6) + F (5) = 8 + 5 = 13 = F (7)$ ✅. Aur $F (0) = 0, F (1) = 1$ definition se match karte hain. ✅

Ex 2 — Coin change count, reachable + zero target (cells C, D)

Worked example

coins=[2,3], count karo kitne ways hain amount = 6 banana; aur amount = 0 bhi confirm karo. Forecast: andaza lagao kitne combinations of 2s aur 3s sum to 6. (Hint: kya $2 + 2 + 2$ unme se ek hai? Kya $3 + 3$ ?)

Step 1 — Base set karo. dp[0] = 1. Yeh step kyun? 0 banane ka bilkul ek hi tarika hai — koi coin mat lo (empty set). Yeh cell D hai. Agar tum ise 0 set karte ho, toh har count baad mein collapse ho jaata hai 0 par, kyunki har real combination "baaki 0 banao" par ja kar khatam hoti hai.

Step 2 — BAAHR coins loop karo. Yeh step kyun? Hume combinations chahiye, ordered sequences nahi. Coin order fix karna (pehle coin 2 ke sab uses dekho, phir coin 3) matlab $2 + 3$ aur $3 + 2$ ek hi cheez mein exactly ek baar count hote hain. (Cell K neeche dikhata hai agar aap aisa nahi karte toh kya tootta hai.)

Coin $2$ : $a = 2 \dots 6$ ke liye dp[a]+=dp[a-2] karo. $[1, 0, \underline{1}, 0, \underline{1}, 0, \underline{1}] \Rightarrow ways with only 2s: a = 0, 2, 4, 6$ Coin $3$ : $a = 3 \dots 6$ ke liye dp[a]+=dp[a-3] karo. $d p [3] + = d p [0] = 1, d p [4] + = d p [1] = 0, d p [5] + = d p [2] = 1, d p [6] + = d p [3] = 1$ Final dp = [1,0,1,1,1,1,2].

Verify karo: dp[6]=2. Haath se enumerate karo: $2 + 2 + 2$ aur $3 + 3$ — bilkul 2. ✅ dp[0]=1 (empty set) ✅.

Ex 3 — Coin change min, greedy trap (cell E)

Worked example

coins=[1,3,4], amount = 6 ke liye minimum coins. Forecast: greedy kehta hai "pehle sabse bada coin lo." Greedy kya deta hai? Real minimum kya hai? Dono andaza lagao.

Step 1 — Greedy kya karta hai (aur kyun tempting lagta hai). $6$ se chota ya barabar sabse bada coin $4$ hai; remainder $2$ , phir $1 + 1$ . Total $4 + 1 + 1 = 3$ coins. Yeh kyun dikhaya? "Acche" systems (1,5,10,25) ke liye greedy optimal hai, isliye log ise zyada trust karte hain — dekho Greedy Algorithms. Yahan ye jhoot bolta hai.

Step 2 — DP har possible last coin try karta hai. dp[0]=0, baki $\infty$ . $dp [a] = min_{c \leq a} (dp [a - c] + 1)$ +1 kyun? Ek extra coin (aakhri wala, $c$ ) baaki $a - c$ banane ke optimal tarike mein add hota hai — optimal substructure. Table:

$a$	0	1	2	3	4	5	6
dp	0	1	2	1	1	2	2

$d p [6] = min (d p [5], d p [3], d p [2]) + 1 = min (2, 1, 2) + 1 = 2$ (coin $3$ se, yaani $3 + 3$ ).

Verify karo: DP $= 2$ ( $3 + 3$ ) beats greedy $= 3$ ( $4 + 1 + 1$ ). ✅ Jab bhi denominations arbitrary hon, DP jeetta hai.

Ex 4 — Coin change min, impossible target (cell F)

Worked example

coins=[2,4], amount = 3 ke liye minimum coins. Forecast: kya tum 2s aur 4s se 3 bana bhi sakte ho? Function ko kya return karna chahiye?

Step 1 — Unreachability pehchano. Saare coins even hain, target odd hai. Evens ka koi combination odd nahi hoga. Yeh step kyun? Ek degenerate/impossible input ko ek sentinel ( $- 1$ ) return karna chahiye, koi garbage number nahi.

Step 2 — Dekho $\infty$ kaise propagate karta hai. dp=[0,∞,∞,∞]. $d p [1]$ : koi coin $\leq 1$ nahi → $\infty$ hi rahega. $d p [2] = d p [0] + 1 = 1$ . $d p [3]$ : sirf coin $2 \leq 3$ , toh $d p [3] = d p [1] + 1 = \infty + 1 = \infty$ . Yeh step kyun? $\infty$ matlab "unreachable"; unreachable mein 1 add karo toh bhi unreachable — $\infty$ ki algebra correctness free mein enforce karti hai.

Step 3 — Sentinel ko answer mein convert karo. return -1 if dp[3]==INF else dp[3] → -1.

Verify karo: $d p [3]$ kabhi $\infty$ se neeche nahi aaya ⇒ return $- 1$ . Parity argument confirm karta hai ye truly impossible hai. ✅

Ex 5 — 0/1 knapsack, ordinary 2D (cell G)

Worked example

w=[1,3,4,5], v=[1,4,5,7], capacity W=7. Forecast: kaun sa subset weight 7 ke andar value maximize karta hai? Value guess karo.

Step 1 — 2D state set up karo. dp[i][w] = pehle $i$ items aur capacity $w$ use karke best value. Row 0 (koi item nahi) aur column 0 (koi capacity nahi) sab zeros hain. 2D kyun? Future ko sirf yahi chahiye ki kitne items bache hain aur kitni capacity bachi hai — yahi dono numbers state hain.

Step 2 — Har cell ko skip-vs-take se fill karo. Figure follow karo: red arrow (skip) seedha neeche copy karta hai; violet arrow (take) $w_{i}$ columns peeche aur ek row upar jaata hai, phir $v_{i}$ add karta hai.

\underbrace{v_i+\text{dp}[i-1][w-w_i]}_{\text{take }i,\ \text{if }w_i\le w}\big)$$ *Lete waqt row $i-1$ ki taraf kyun dekho?* Item $i$ **zyada se zyada ek baar** use hota hai; use lene ke baad hume sirf *pehle waale* items ke saath continue karna hai — isliye previous row. Final cell `dp[4][7] = 9`. **Verify karo:** items 2 & 3 ka weight $3{+}4=7\le7$ aur value $4{+}5=9$ hai. Item 4 akela $=7$; item $1{+}4$ $=8$. Toh **9** best hai. ✅

Ex 6 — 0/1 knapsack, degenerate (zero capacity / item bahut bhaari) (cell H)

Ex 7 — 0/1 knapsack, 1D reverse-loop, concrete roop mein (cell I)

Worked example

w=[2], v=[3], capacity W=6. 1D array ko dono loop directions mein run karo aur difference dekho. Forecast: weight 2 ke EK item ke saath, tum ise zyada se zyada ek baar le sakte ho (0/1). Max value $3$ honi chahiye. Forward loop galat kya deta hai?

Step 1 — Sahi: weight NEECHE ki taraf iterate karo. dp=[0,0,0,0,0,0,0], item weight 2, value 3. $w = 6, 5, 4, 3, 2$ ke liye: dp[w]=max(dp[w], 3+dp[w-2]). Kyunki hum neeche jaate hain, dp[w-2] abhi bhi purani (item-not-yet-used) value $0$ rakhta hai, isliye har dp[w] $max (0, 3 + 0) = 3$ ho jaata hai. Final dp[6]=3. Neeche kyun? Yeh guarantee karta hai ki dp[w-2] us state ki taraf point karta hai is item se pehle wali — matlab "item ek baar use karo."

Step 2 — Galat: weight AAGE ki taraf iterate karo (bug expose karne ke liye). $w = 2, 4, 6$ ke liye: $d p [2] = 3$ ; phir $d p [4] = 3 + d p [2] = 6$ ; phir $d p [6] = 3 + d p [4] = 9$ . Yeh item ko teen baar use kar raha hai — yeh unbounded knapsack hai, 0/1 nahi.

Verify karo: downward → dp[6]=3 (item ek baar liya) ✅. Forward → dp[6]=9 (item teen baar liya) — clearly 0/1 ke liye galat paradigm. ✅

Ex 8 — Word problem: hiker ka backpack (cell J)

Worked example Ek hiker ka pack

10 kg uthaa sakta hai. Available gear: tent (4 kg, 30 pts ki value), stove (3 kg, 20 pts), sleeping bag (5 kg, 40 pts), camera (2 kg, 15 pts). Har item unique hai (lo ya chhod do). Points maximize karo. Forecast: andaza lagao use kaunse items lene chahiye.

Step 1 — Story ko DP mein translate karo. Yeh step kyun? "Unique item, take-or-leave, weight budget, value maximize karo" bilkul literally 0/1 knapsack hai. w=[4,3,5,2], v=[30,20,40,15], W=10.

Step 2 — Weight 10 ke andar candidate subsets ke baare mein soocho.

tent + sleeping bag + camera $= 4 + 5 + 2 = 11 > 10$ ✗ (budget se bahar)
tent + stove + camera $= 4 + 3 + 2 = 9 \leq 10$ , value $30 + 20 + 15 = 65$
sleeping bag + tent $= 5 + 4 = 9 \leq 10$ , value $40 + 30 = 70$
sleeping bag + stove + camera $= 5 + 3 + 2 = 10 \leq 10$ , value $40 + 20 + 15 = 75$

Weight pehle kyun check karo? Capacity guard constraint hai; value sirf feasible subsets mein matter karti hai.

Step 3 — DP max confirm karta hai. 0/1 table return karta hai dp[4][10] = 75.

Verify karo: best feasible subset = {sleeping bag, stove, camera}, weight $10$ , value 75 — koi feasible subset isse beat nahi karta. ✅ (Units: kg ≤ 10 ✔, points summed ✔.)

Ex 9 — Exam twist: count vs permutations (loop order meaning badal deta hai) (cell K)

Worked example

coins=[1,2], target=3. Compute karo (a) combinations ki sankhya aur (b) ordered sequences (permutations) ki sankhya. Same recurrence, alag loop order. Forecast: kaun sa number bada hai, aur kyun?

Step 1 — Combinations (coins BAAHR). dp[0]=1. Coin 1: dp=[1,1,1,1]. Coin 2: $d p [2] + = d p [0] = 2, d p [3] + = d p [1] = 2$ → dp=[1,1,2,2]. dp[3]=2: sets ${1, 1, 1}$ aur ${1, 2}$ . Coins baahr kyun? Yeh ek coin ko naye order mein dobara visit karna rokta hai, isliye $1 + 2$ aur $2 + 1$ ek mein collapse ho jaate hain.

Step 2 — Permutations (amount BAAHR, coins andar). dp[0]=1. $a = 1 \dots 3$ ke liye: dp[a]=sum(dp[a-c] for c in coins, c<=a). $d p [1] = d p [0] = 1; d p [2] = d p [1] + d p [0] = 2; d p [3] = d p [2] + d p [1] = 2 + 1 = 3$ . dp[3]=3: ordered sequences $1 + 1 + 1, 1 + 2, 2 + 1$ . Amount baahr kyun? Ab sequence ki har position koi bhi coin freely choose kar sakti hai, isliye order count hota hai.

Verify karo: combinations $= 2$ , permutations $= 3$ . Permutations $\geq$ combinations kyunki ordering ${1, 2}$ ko do arrangements mein tod deti hai. ✅ Exam takeaway: recurrence same hai; sirf loop order decide karta hai combinations vs permutations — dekho Tabulation vs Memoization.

Recall Self-test (jawab dene ke baad reveal karo)

Coin-change min coins=[2,4], amount=3 ke liye $- 1$ kyun return karta hai? ::: Saare coins even hain; odd target unreachable hai, isliye dp[3] $\infty$ par hi rehta hai aur $- 1$ mein convert ho jaata hai. 1D 0/1 knapsack mein kaun sa loop direction sahi hai aur kyun? ::: Downward — yeh dp[w-w_i] ko us state ki taraf point karta hai current item se pehle wali, jo "har item zyada se zyada ek baar use karo" enforce karta hai. Coin-change count ke liye dp[0] kya hai aur kyun? ::: $1$ — amount 0 banane ka exactly ek tarika hai: empty set. Same recurrence, coins-outside vs amount-outside se kya do alag meanings milti hain? ::: Coins outside = combinations (order ignore); amount outside = permutations (order count).