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

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

Do words jinpar hum constantly rely karte hain, ek baar define karte hain taaki koi symbol undefined na rahe:

True ya false — justify karo

Har DP problem ko 2D table chahiye.

False. Fibonacci aur coin change 1D hain; table ki shape un cheezों ki sankhya ke barabar hoti hai jinpar future actually depend karta hai (iska "state"). Sirf tab 2D chahiye jab do independent quantities matter karein (item index aur remaining capacity).

Memoization aur tabulation hamesha exactly wahi subproblems compute karte hain.

False. Memoization (top-down) sirf wahi subproblems compute karta hai jintak recursion actually pahunchti hai; tabulation (bottom-up) puri table fill karta hai, un cells ko bhi jo kabhi needed na hon. Dekho Tabulation vs Memoization.

Agar kisi problem mein optimal substructure hai, toh woh zaroor DP problem hai.

False. Optimal substructure akele (bina repeated subproblems ke) simple divide-and-conquer hota hai — merge sort mein optimal substructure hai lekin zero overlap, isliye caching kuch nahi khareerti.

Coin-change count mein dp[0] = 1 isliye kyunki zero ek coin hai.

False. dp[0] = 1 ka matlab hai amount 0 banane ka exactly ek tarika hai — empty selection (kuch use mat karo). Yeh ways ki count hai, coins ki count nahi.

Coin-change min mein dp[0] = 0 usi karan isliye jisme count dp[0] = 1 use karta hai.

False. Alag meaning: min coins count karta hai, aur 0 banane mein zero coins chahiye, isliye dp[0] = 0. Count ways measure karta hai (ek tarika: empty), min coins measure karta hai (zero coins). Same cell, alag quantity.

Greedy (sabse bada coin pehle lo) hamesha minimum number of coins deta hai.

False. Sirf "canonical" systems jaise 1,5,10,25 ke liye. Coins = [1,3,4], target 6 ke liye, greedy 4+1+1 = 3 coins deta hai lekin DP 3+3 = 2 find karta hai. Greedy ka arbitrary denominations ke liye optimal substructure guarantee nahi hai.

0/1 knapsack aur unbounded knapsack mein fark sirf itna hai ki 1D version mein weight loop upar jaata hai ya neeche.

True. 1D form mein, weight ko neeche iterate karne par dp[w-wi] abhi bhi previous item hold karta hai (zyada se zyada ek baar use → 0/1); upar iterate karne par dp[w-wi] mein pehle se item i aa sakta hai (reuse → unbounded). Ek direction flip hi poora fark hai.

Naive recursive Fibonacci slow isliye hai kyunki addition slow hai.

False. Yeh slow isliye hai kyunki recursion tree mein ≈ φⁿ nodes hain — wahi F(k) exponentially kaafi baar recompute hota hai. Memory repeats ko khatam karti hai, faster arithmetic nahi. Dekho Time and Space Complexity.

Space-optimized Fibonacci (do variables rakhna) time complexity badal deta hai.

False. Time Θ(n) hi rehta hai; sirf space Θ(n) se Θ(1) tak girti hai. Space aur time independent axes hain — table trim karna additions ki sankhya kam nahi karta.

Coin-change count mein loops swap karne par (amount bahar, coins andar) bhi sahi answer milta hai.

False. Coins bahar combinations count karta hai; amount bahar rakhne se permutations count hoti hain, isliye 1+2 aur 2+1 alag-alag count hote hain aur total inflate ho jaata hai.

Error dhundo

"0/1 knapsack ke liye maine 1D array mein weight forward loop kiya — yeh coin-count se match kiya isliye theek hoga."

Galat. Forward iteration se dp[w-wi] mein pehle se item i aa sakta hai, isliye item i reuse ho jaata hai → tumne silently unbounded knapsack likh diya. Fix: w ko W se wi tak neeche loop karo.

"Coin min recurrence: dp[a] = min(dp[a-c]) — sabse chhhota sub-answer lo."

+1 missing hai. "Last coin c" choose karne par ek coin spend hoti hai, isliye yeh dp[a-c] + 1 hai. +1 ke bina har dp dp[0] ki taraf collapse ho jaata hai aur bahut kam coins report karta hai.

"0/1 knapsack recurrence 'take' branch ke liye dp[i][w-wi] use karta hai."

Galat row. Yeh dp[i-1][w-wi] hona chahiye. Row i reference karne par item i dobara liya ja sakta hai — yeh reuse hai, jo 0/1 mana karta hai. i-1 hi "zyada se zyada ek baar" enforce karta hai.

"Coin min mein unreachable amounts 0 se start hone chahiye."

Galat. Inhe ∞ (ek sentinel jiska matlab "impossible" hai) se start karna hoga. 0 se start karne par min() khushi se impossible amounts nothing se bana leta hai aur ek galat chhhoti count return karta hai.

"Fibonacci memo dictionary as a default argument def fib(n, memo={}) ek clean idiom hai."

Khatarnak. Ek mutable default sabhi calls mein share hota hai, isliye cache alag top-level invocations ke beech leak karta hai. Yahan yeh speed up karta hai, lekin yeh ek well-known trap hai; memo explicitly pass karo ya None use karo. Dekho Recursion and Memoization.

"0/1 knapsack mein 'skip' branch dp[i-1][w] kabhi kabhi dp[i-1][w-wi] hona chahiye."

Galat. Item i skip karne ka matlab capacity untouched rehti hai, isliye weight w hi rehta hai. Sirf take branch wi subtract karta hai. Inhe mix karna state ke meaning ko corrupt kar deta hai.

Why questions

Coin-count mein dp[0] = 1 kyun set karna chahiye, 0 nahi?

Kyunki dp[a] += dp[a-c] ko ek nonzero seed chahiye: exact value a ki ek coin ek valid way count honi chahiye, aur woh way hai "a-c=0 kuch nahi se banao, phir c add karo." dp[0]=1 woh single empty way inject karta hai taaki propagate ho sake.

Coins ko bahar loop karne par combination double-count kyun nahi hote?

Yeh coin ka ek order fix kar deta hai. Ek baar coin c ka loop khatam ho jaata hai, baad ke coins sirf c ke baad add ho sakte hain, isliye combination ek canonical order mein banta hai — 1+2 exist karta hai lekin 2+1 ko doosra path kabhi nahi milta.

0/1 knapsack ko apne state mein capacity kyun chahiye lekin Fibonacci ko nahi?

Fibonacci ka future sirf kis index par ho is par depend karta hai. Knapsack ka future do cheezein par depend karta hai — kaunse items baaki hain aur kitni room bachi hai — isliye ek single index state describe nahi kar sakta.

Coin-min mein +1 kyun hai lekin coin-count mein += hai?

Min ek cost measure karta hai, isliye ek aur coin use karna total mein 1 add karta hai (+1). Count kitne tarike exist karte hain measure karta hai, isliye ek coin choose karna cost add nahi karta — yeh sub-target ke saare tarike current count mein pool karta hai (+=).

1D knapsack mein reverse (downward) weight loop "previous item" ko preserve kyun karta hai?

High→low jaane par, jab tum dp[w] update karte ho tum dp[w-wi] read karte ho, jo ek lower index hai is round mein abhi tak touch nahi hua — isliye yeh abhi bhi row i-1 ki value hold karta hai. Low→high jaane par, dp[w-wi] pehle se item i se overwrite ho chuka hota hai.

Greedy 1,5,10,25 se change banane ke liye valid kyun hai lekin [1,3,4] ke liye nahi?

1,5,10,25 ke saath har bada coin ek "clean" multiple-ish jump hai isliye sabse bada grabbing tumhe kabhi trap nahi karta. [1,3,4] ke saath, target 6 ke liye 4 grab karna tumhe 2 par chhod deta hai (do 1s chahiye), jabki do 3s saste the — greedy ke paas yahan optimality ka koi proof nahi hai.

Fibonacci mein sirf last do values rakh sakte hain lekin knapsack (2D) mein nahi — kyun?

F(i) sirf neeche ke do rows par depend karta hai, isliye 2 ka rolling window kaafi hai. Knapsack ka dp[i][w] poori previous row par depend karta hai saari capacities ke liye, isliye tum ek poori row rakhte ho (yahi karan hai ki 1D knapsack ek array rakhta hai, do scalars nahi).

Edge cases

Coin change (count) jab amount = 0.

Answer 1 hai, 0 nahi — empty selection 0 banata hai. Yahi wajah hai ki dp[0] 1 se initialize hota hai; "trivial" case ek real combination hai.

Coin change (min) jab amount unreachable ho (jaise coins=[2], amount=3).

dp[amount] ∞ rehta hai, aur function -1 return karta hai. ∞ sentinel hi hai jo tumhe impossibility detect karne deta hai galat finite number return karne ki jagah.

Knapsack jab capacity W = 0 ho.

Answer 0 value hai — koi item fit nahi hota, aur poori dp row 0 hai. Base row/column ke zeros pehle se yeh encode karte hain; koi special case nahi chahiye.

Knapsack jahan har item ka weight W se zyada ho.

"Take" branch kabhi enable nahi hota (iska guard wi ≤ w hamesha fail karta hai), isliye dp sab-skip ho jaata hai aur 0 return karta hai. Kuch nahi toot ta — guard automatic handle kar leta hai.

Fibonacci jab n = 0 aur n = 1.

F(0)=0 aur F(1)=1 base cases hain; loop/recurrence sirf n ≥ 2 par shuru hota hai. Koi bhi base case bhoolna poori sequence shift kar deta hai ya pehli recursive call par crash kar deta hai.

Coin change jab coin list empty ho.

Count sirf amount 0 ke liye 1 hai (empty set) aur kisi bhi positive amount ke liye 0; min kisi bhi positive amount ke liye -1 return karta hai. Base cases abhi bhi hold karte hain — coins par loops simply kabhi execute nahi hote.

Subset-sum framing: kya 0/1 knapsack logic decide kar sakta hai ki target sum reachable hai?

Haan — har item ki value uske weight ke barabar set karo (ya boolean reachability table use karo); yeh wahi "take/skip, at most once" structure hai. Dekho Subset Sum and Partition Problems.

Kya unbounded knapsack kabhi 0/1 knapsack ke barabar hota hai?

Haan, jab kisi bhi item ka weight itna chhhota na ho ki W ke andar do baar fit ho sake — reuse impossible ho jaata hai, isliye up-loop aur down-loop identical answers dete hain. Dekho Unbounded Knapsack and Rod Cutting.

Recall Is page band karne se pehle ek-line self-test

Zor se bolo: count → coins outside; min → +1, ∞ for unreachable; 0/1 → weight down, row i-1; unbounded → weight up, row i. Agar in chaar mein se koi bhi arbitrary lagta hai, toh matching "Why" dobara padho.