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

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

Step 0 — Actual sawaal kya hai?

Koi bhi math se pehle, situation imagine karo.

Figure dekho: teen items ek bag ke bahar rakhe hain jis par "capacity $W = 7$ " likha hai. Hume har ek ke liye decide karna hai — andar ya bahar. Yeh $2^{n}$ possible subsets hain — $n = 30$ ke liye ek billion hota hai. Hum chahte hain in sab ko check karne se zyada smart approach use karein.

Step 1 — Choice ko ek repeatable sawaal mein badlo

KYA. Hum ek waqt mein EK item attack karte hain. Items ko item 1, item 2, …, item $n$ ke order mein lagaao. Item $i$ ke saamne khade ho aur ek simple haan/na sawaal poochho: kya main item $i$ bag mein daalta hun?

KYUN. Haan/na sawaal ke sirf do branches hote hain. Agar hum "best value using items $1.. i$ with a bag of size $w$ " ko sirf "best value using items $1.. i - 1$ " dekh ke solve kar sakte hain, toh humne ek item problem se hataa diya — ek strictly chota problem jo same shape ka hai. Dynamic programming ka yahi poora trick hai: recursion jahan har call original ka ek chota version hota hai.

PICTURE.

Tree mein pehla fork dikhta hai. Left branch (blue) = "item $i$ skip karo". Right branch (orange) = "item $i$ lo". Notice karo ki dono children ab sirf items $1.. i - 1$ ke baare mein baat karte hain — item $i$ khatam ho jaata hai jis waqt hum decide karte hain. Yahi sab kuch ka beej hai.

Hum chote problem ke answer ko yeh naam dete hain:

$dp [i] [w] = best total value using only items 1.. i, with a bag of capacity w$

Term by term:

$i$ — kitne items hum consider karne ki permission rakhte hain (ek prefix $1.. i$ ).
$w$ — abhi bag mein kitni capacity baaki hai kharch karne ke liye, $0 \leq w \leq W$ .
$dp [i] [w]$ — woh number jo hum dhundh rahe hain: in dono limits ke andar maximum value jo mil sakti hai.

Step 2 — "Skip" branch

KYA. Maan lo hum item $i$ nahi lete.

KYUN. Agar item $i$ kabhi andar nahi jaata, toh jo bhi value humein milegi woh poori tarah items $1.. i - 1$ se aayegi, aur bag capacity unchanged rahegi — abhi bhi $w$ . Toh hum best yahi kar sakte hain jo ek kam item aur same room ke saath pehle se kar sakte the:

$answer if we skip dp [i] [w] = same room, one fewer item dp [i - 1] [w]$

$i - 1$ — item $i$ menu se chala gaya, toh hum previous prefix par wapas jaate hain.
$w$ (unchanged) — skip karne mein koi weight nahi lagta, toh capacity same rehti hai.

PICTURE.

Blue arrow seedha ek row upar (row $i$ se row $i - 1$ tak) jaata hai aur same column $w$ mein rehta hai. Seedha upar = "ek kam item"; same column = "capacity kharch nahi hui". Woh vertical arrow hi skip rule hai.

Step 3 — "Take" branch

KYA. Ab maan lo hum item $i$ lete hain.

KYUN. Jis waqt item $i$ bag mein jaata hai, do cheezein hoti hain:

Hume uski value $v_{i}$ milti hai.
Hum apni capacity mein se $w_{i}$ kharch karte hain, sirf $w - w_{i}$ baaki rehti hai baaki sab ke liye. Aur "baaki sab" items $1.. i - 1$ se hi aana chahiye (kyunki item $i$ use ho gaya — yeh 0/1 rule hai: doosri copy nahi). Toh:

$answer if we take dp [i] [w] = value we gain v_{i} + previous items only dp [i - 1] [shrunken room w - w_{i}]$

$v_{i}$ — item $i$ ko andar rakhne ka reward; ek baar add hota hai.
$i - 1$ — phir se ek row neeche aate hain, kyunki item $i$ reuse nahi ho sakta.
$w - w_{i}$ — bag mein ab kam jagah hai; hum sub-problem se reduced capacity ke baare mein poochh rahe hain.

Guard condition. Yeh branch tab hi kaam ka hai jab item fit ho: hamein chahiye $w_{i} \leq w$ . Agar $w_{i} > w$ hai toh item current bag ke liye bahut bhaari hai, toh "take" impossible hai aur sirf skip branch bachta hai.

PICTURE.

Orange arrow ek row upar AND $w_{i}$ columns left jaata hai (column $w$ se column $w - w_{i}$ tak), phir hum upar se $v_{i}$ add karte hain. Upar = kam items; left = capacity kharch hui; " $+ v_{i}$ " label arrow par chadha hai = collect ki gayi value.

Step 4 — Combine: dono branches mein se better lo

KYA. $dp [i] [w]$ ke liye hamare paas do candidate values hain: skip value aur take value. Jo bada ho, woh rakhte hain, kyunki hum maximum value chahte hain.

$max$ kyun, $+$ kyun nahi? Yeh do branches ek hi cell ke liye mutually exclusive decisions hain — item $i$ ya to andar hai ya bahar, kabhi dono nahi. Toh hum inhe add nahi karte; winner choose karte hain. $max$ exactly yeh jawaab deta hai — "kaunsa ek decision mujhe zyada amir banata hai?"

$dp [i] [w] = max (skip (Step 2) dp [i - 1] [w], take (Step 3), only if w_{i} \leq w v_{i} + dp [i - 1] [w - w_{i}])$

PICTURE.

Steps 2 aur 3 ke dono arrows ab same target cell (green) mein feed hote hain. Chota " $max$ " gate oonchi bar rakhta hai. Poori table ka har cell isi ek gate se bharta hai — yahi poora algorithm hai.

Base row. Row $i = 0$ ka matlab hai "zero items allowed". Koi item nahi toh kuch bhi nahi rakh sakte, toh value $0$ hai har capacity $w$ ke liye: $dp [0] [w] = 0$ . Yahi woh floor hai jis par poori table tikhi hai.

Step 5 — Poori table bharo, ek real example dekho

KYA. Row by row, left to right, sirf do arrows use karke bharo. Parent se example: $w = [1, 3, 4, 5], v = [1, 4, 5, 7], W = 7$

KYUN row order. Har cell $dp [i] [w]$ sirf row $i - 1$ dekhti hai (dono arrows upar jaate hain). Toh jab tak current row shuru karne se pehle previous row complete ho, har zaroorat ki value pehle se ready hai. Koi cell read hone se pehle likhi nahi jaati.

PICTURE.

Colour-shaded grid finished table hai. Bottom-right corner trace karo $dp [4] [7] = 9$ . Winning path (highlighted) item 2 (weight 3, value 4) aur item 3 (weight 4, value 5) lene se aayi: $3 + 4 = 7$ weight exactly, $4 + 5 = 9$ value. Kyunki har "take" arrow ek row drop karta hai, item 2 aur item 3 mein se har ek ek baar use hota hai — 0/1 ka vaada automatically pura hota hai.

Step 6 — Do rows ko ek mein squeeze karo (aur loop reverse kyun hota hai)

KYA. Notice karo ki har naya row sirf directly upar wala row padhta hai. Toh hume kabhi poori 2D grid ki zaroorat nahi — ek 1D array dp[w] jo hum overwrite karte jaate hain jab bhi koi item process karte hain, woh kaafi hai.

KYUN inner loop reverse karo. Jab hum ek single row in-place overwrite karte hain, toh jo cell hum padhte hain, $dp [w - w_{i}]$ , usme abhi bhi puraani (previous-item) value honi chahiye — kabhi bhi freshly updated current-item value nahi. Agar hum left→right jaayein, toh hum $dp [w - w_{i}]$ ko padhne se pehle update kar denge, isse item $i$ do baar ghus sakta hai. Right→left jaana ( $W$ se $w_{i}$ tak neeche) guarantee karta hai ki $dp [w - w_{i}]$ abhi bhi previous item ki value hai jab hum use karte hain.

PICTURE.

Top strip: forward iteration — red arrow left mein ek aisi cell padhta hai jo is round mein already refresh ho chuki hai, toh item $i$ phir se ghus jaata hai (yeh unbounded knapsack hai, dekho Unbounded Knapsack and Rod Cutting). Bottom strip: backward iteration — green arrow hamesha ek "puraani" cell padhta hai, toh har item zyada se zyada ek baar andar jaata hai. Same code, bas ek loop direction ka fark.

Step 7 — Har edge case, dikhaya gaya

KYA & KYUN. Ek sahi derivation weird inputs mein bhi survive karni chahiye. Yeh rahi woh cases:

$W = 0$ (bag kuch nahi rakh sakta): take branch ko $w_{i} \leq 0$ chahiye, positive weights ke liye impossible, toh har cell $0$ hai. Answer $= 0$ . (leftmost panel)
Koi item nahi ( $n = 0$ ): base row hi poori table hai; answer $= 0$ . (second panel)
Ek item bag se zyada bhaari ( $w_{i} > W$ ): uska take arrow column $w - w_{i} < 0$ par jaayega, jo exist nahi karta — toh woh item kabhi nahi liya ja sakta aur sirf uska skip arrow fire karta hai. (third panel — item greyed out dikhaya gaya hai)
Zero-value item ( $v_{i} = 0$ ): ise lene se $+ 0$ milta hai lekin weight khaata hai, toh $max$ ise tabhi pick karega jab koi nuksan na ho; yeh optimum ko kabhi hurt nahi karta. (rightmost panel)
Saare items ek saath fit ho jaate hain ( $\sum w_{i} \leq W$ ): har take branch available hai, toh optimum simply $\sum v_{i}$ hai — bag kabhi bottleneck nahi banta.

Kyunki recurrence max(skip, take-if-fits) hai all-zeros base ke saath, in mein se kisi case ke liye special code ki zaroorat nahi — yeh sab same do arrows se nikal aate hain. Yahi robustness hai — ise memorize karne ki jagah derive karne ka yeh faida hai.

Ek-picture summary

Ek target cell, do arrows, ek $max$ gate, zeros ki ek base row — ek grid mein repeat, phir ek single backward-swept array mein fold kar diya. Is page par sab kuch wahi picture hai.

Recall Feynman retelling — walkthrough ko ek 12-saal ke bacche ko samjhao

Apne toys line karo. Ek backpack lo jo ek certain weight rakh sakta hai. Pehle toy ke paas jao aur do cheezein poochho: "Agar main ise chod dun, toh pichhle toys aur itni room ke saath main kitna khush hounga?" — yeh grid mein seedha upar dekhna hai. "Agar main ise uthaa lun, toh mujhe uske fun points milenge lekin backpack mein pehle wale toys ke liye kam room bachega" — yeh upar-aur-left dekhna hai, phir fun points add karna. Jo jawaab tumhe zyada khush kare, wahi rakho. Yeh har toy ke saath har possible room amount ke liye karo, har jawaab ek sticky note par likhte jao taaki kabhi redo na karo. Jab ek sticky-note row se kaam chalao paper bachane ke liye, use sabse badi room se sabse choti room tak bharo, taaki kabhi ek hi toy do baar count na ho. Aakhri sticky note, bottom-right, tumhari best possible khushi hai.

Recall

"Take" arrow row $i - 1$ par kyun jaata hai, row $i$ par kyun nahi? ::: Kyunki 0/1 knapsack mein har item zyada se zyada ek baar use hota hai; item $i$ lene ke baad hume sirf pehle ke items ke saath continue karna hai. Dono branches ko add karne ki jagah $max$ kyun? ::: Skip aur take same cell ke do mutually exclusive decisions hain; hum better wala pick karte hain, dono nahi karte. 1D version mein weight $W$ se $w_{i}$ tak iterate kyun karte hain? ::: Taaki jab $dp [w - w_{i}]$ padhte hain tab usme abhi bhi previous item ki value ho, ek item ko do baar lene se rokne ke liye. $dp [0] [w]$ kya hai aur kyun? ::: Saare $w$ ke liye $0$ — zero items allowed hone par kuch pack nahi kar sakte, toh koi value nahi.

Yeh bhi dekho: Tabulation vs Memoization · Time and Space Complexity · Subset Sum and Partition Problems · Greedy Algorithms · parent topic.