Tabulation (bottom-up DP) — iterative: Worked examples

3.7.8 · D3 · Coding › Algorithm Paradigms › Tabulation (bottom-up DP) — iterative

Yeh parent Tabulation note ka "sleeves chadhao aur karo" companion hai. Wahan humne 5-step recipe seekhi thi (State, Recurrence, Base, Order, Answer). Yahan hum use har tarah ke case ke khilaf stress-test karenge jo ek tabulation problem de sakti hai — including woh ugly wale jo parent note ne sirf hint kiye the.

Shuru karne se pehle, ek promise: har symbol kamaya hua hai. dp[i] ka matlab sirf "woh answer jo humne boxes ki ek list mein box number $i$ mein store kiya." Ek table woh boxes ki list hai. Shelf par rakhe labelled shoeboxes ki ek row se zyada mysterious kuch nahi.

Scenario matrix

Ek tabulation problem ko ek machine ki tarah socho. Kaise inputs use jam kar sakte hain? Yeh hai "case classes" ka poora menu — neeche har worked example tagged hai un cell(s) ke saath jo woh cover karta hai.

Cell	Case class	Tricky kyon hai	Covered by
C1	1D table, additive recurrence	easy baseline	Ex 1
C2	Degenerate / tiny input ( $n = 0$ , empty set)	base case hi poora answer hai	Ex 2
C3	2D table, binary "take/skip" choice	previous row se do dependencies	Ex 3
C4	Impossible / "no solution" state	$\infty$ ya $- 1$ safely represent karna zaroori	Ex 4 (Coin Change)
C5	Order matters — galat loop direction sab bigaad deta hai	high→low vs low→high	Ex 5
C6	Do strings, 2D grid, match-vs-mismatch	diagonal dependency	Ex 6 (LCS)
C7	Real-world word problem	English → state translate karna	Ex 7
C8	Exam twist: ek "trap" recurrence	obvious recurrence galat hai	Ex 8

Hum aath examples mein aath cells cover karenge. Chalo shuru karte hain.

Ex 1 — C1: additive baseline (Tribonacci)

Forecast: aage padhne se pehle guess karo ki $T (6)$ 10 ke kareeb hai ya 25 ke.

State. dp[i] = $i$ -waan Tribonacci number. Yeh step kyon? Hum pehle box ka naam rakhte hain taaki recurrence ke paas kuch concrete ho fill karne ke liye.
Recurrence. dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Yeh step kyon? Definition literally teen predecessors ko sum karti hai — yahi optimal substructure hai.
Base cases. dp[0]=0, dp[1]=1, dp[2]=1. Yeh step kyon? $i = 2$ par recurrence dp[-1] padhti, jo exist nahi karta. Deepest reach-back cover karne ke liye hume enough boxes seed karne honge (yahan, 3 boxes).
Order. Increasing $i$ . Yeh step kyon? Jab hum dp[i] fill karte hain, dp[i-1], dp[i-2], dp[i-3] sab already likhe hue hain.
Answer. dp[6].

Shelf ko left se right fill karna — main har naya box words mein likhta hoon taaki kuch loop ke andar chhupa na rahe:

dp[3] $= d p [2] + d p [1] + d p [0] = 1 + 1 + 0 = 2$ .
dp[4] $= d p [3] + d p [2] + d p [1] = 2 + 1 + 1 = 4$ .
dp[5] $= d p [4] + d p [3] + d p [2] = 4 + 2 + 1 = 7$ .
dp[6] $= d p [5] + d p [4] + d p [3] = 7 + 4 + 2 = 13$ .

i	0	1	2	3	4	5	6
dp[i]	0	1	1	2	4	7	13

Verify: 3 consecutive earlier boxes ki kisi bhi window ka sum agla deta hai — e.g. $d p [6] = d p [5] + d p [4] + d p [3] = 7 + 4 + 2 = 13$ . ✅ Answer 13 (10 ke kareeb — kya tumhara forecast sahi nikla?).

Ex 2 — C2: degenerate input

Forecast: zero stairs — kya answer 0 ways hai, ya 1 way?

State. dp[i] = step $i$ tak pahunchne ke distinct ways ki sankhya. Yeh step kyon? Hume decide karna hoga ki "step 0 tak pahunchne" ka matlab kya hai answer dene se pehle.
Base case reasoning. "Zero stairs chadhne" ka exactly ek tarika hai: kuch mat karo. Moves ka woh empty sequence ek valid way hai. Yeh step kyon? Yahan sabse common bug dp[0]=0 likhna hai. Lekin 0 matlab hoga "impossible," jo galat hai — khari rehna ek way hai.
Koi recurrence nahi chalti. $n = 0$ ke liye woh loop jo dp[2], dp[3], … fill karta, woh kabhi start hi nahi hota (index 2 aur index 0 ke beech kuch nahi hai). Toh answer seedha base cell se padha jaata hai — yeh exactly woh case hai jahan base case hi poora answer hai.
Answer. dp[0] = 1.

Verify: $d p [0] = 1$ ; aur downstream $d p [2] = d p [1] + d p [0] = 2$ (do real ways: 1,1 aur 2). ✅ Answer 1 way.

Ex 3 — C3: 2D take/skip (0-1 Knapsack full trace)

Forecast: kya hum value 5 se better kar sakte hain?

Pehle, notation — har symbol use se pehle define:

Hum ek grid banate hain: rows = "pehle $i$ items available", columns = "capacity $c$ 0 se 4 tak." dp[i][c] = pehle $i$ items use karke capacity $c$ ke saath best value.

Recurrence (parent note se), ab ki $w_{i}, v_{i}, c$ sab define ho gaye hain: $d p [i] [c] = {d p [i - 1] [c] max (d p [i - 1] [c], v_{i} + d p [i - 1] [c - w_{i}]) w_{i} > c w_{i} \leq c$

Previous row se do dependencies kyon? Kyunki item $i$ ya toh bahar hai (same $c$ par upar wali row copy karo) ya andar hai (uski value $v_{i}$ plus earlier items ki best packing leftover capacity $c - w_{i}$ mein — woh bhi upar wali row se).

Neeche di gayi figure exactly yeh do arrows dikhati hai. Ise aise padho: yellow cell (neeche, pink ?) woh dp[i][c] hai jo hum compute kar rahe hain. Upar se seedha neeche wala blue arrow "skip" choice hai — woh dp[i-1][c] copy karta hai. Pink diagonal arrow dp[i-1][c-w_i] se aata hai jo aur left hai (leftover capacity $w_{i}$ pay karne ke baad) aur "take" choice represent karta hai, jisme hum $v_{i}$ add karte hain. Jo bada hoga woh rakh lete hain.

Figure — Tabulation (bottom-up DP) — iterative

Row 0 (koi item nahi) = sab zeros — zero items available hone par tum kabhi value nahi kama sakte, capacity chahe kuch bhi ho. Ab har cell words mein fill karo:

Row 1, item $(w_{1} = 1, v_{1} = 1)$ . Har $c \geq 1$ ke liye: skip = 0, take = $1 + d p [0] [c - 1] = 1 + 0 = 1$ . Toh dp[1][1..4] sab 1 ho jaate hain; dp[1][0]=0 (weight 1 bhi fit nahi hoti).
Row 2, item $(w_{2} = 3, v_{2} = 4)$ . dp[2][0]=dp[2][1]=dp[2][2]= row 1 copy (weight 3 fit nahi hoti) $= 0, 1, 1$ . dp[2][3]: skip $= 1$ , take $= 4 + d p [1] [0] = 4$ ; max $= 4$ . dp[2][4]: skip $= d p [1] [4] = 1$ , take $= 4 + d p [1] [4 - 3] = 4 + d p [1] [1] = 4 + 1 = 5$ ; max $= 5$ .
Row 3, item $(w_{3} = 4, v_{3} = 5)$ . $c < 4$ wale cells row 2 copy karte hain. dp[3][4]: skip $= d p [2] [4] = 5$ , take $= 5 + d p [2] [0] = 5 + 0 = 5$ ; max $= 5$ (ek tie — item 3 akela items 1+2 ke barabar hai).

$i \ c$	1	2	3	4
0 (none)	0	0	0	0
1 (1,1)	1	1	1	1
2 (3,4)	1	1	4	5
3 (4,5)	1	1	4	5

Order. Rows increasing. Yeh step kyon? Har read row $i - 1$ se hoti hai, jo already finish hai.
Answer. Bottom-right cell dp[3][4] = 5.

Verify: $W = 4$ fit karne wale sab subsets enumerate karo: {} →0, {1}→1, {2}→4, {3}→5, {1,2}: w=4,v=5 ✓, {1,3}: w=5 ✗, {2,3}: w=7 ✗, {1,2,3}: w=8 ✗. Best feasible value = 5. ✅

Ex 4 — C4: "impossible" state (Coin Change — minimum coins)

Forecast: greedy ek 4 pakad leta, phir 2 chahiye → 4+1+1 = teen coins. Kya hum isse better kar sakte hain?

Yahan table mein ek impossible entry ho sakti hai — kuch amounts unmakeable ho sakte hain. Hume ek aisi value chahiye jo "no solution" ka matlab de aur min mein survive kare.

Definition Infinity sentinel — actually store kaise karein

Ek sentinel ek stand-in value hai jo matlab hai "yahan abhi koi answer nahi." Ek minimisation table ke liye hum chahte hain ki woh kisi bhi real answer se bada ho, taaki min(real, sentinel) hamesha real ko rakhe. Code mein likhne ke do safe tarike:

Language infinity use karo: Python mein INF = float('inf'). Phir 1 + INF abhi bhi INF hai, toh impossible paths kabhi min nahi jeetten.
Ek big constant use karo: INF = amount + 1 (koi bhi value strictly coin count ki largest possible value se badi, kyunki tumhe kabhi amount se zyada value-1 coins ki zaroorat nahi padegi). Overflow se bachne ke liye dp[a-c] != INF check karo add karne se pehle, ya simply value ko cap karo.

min ke andar sentinel ki jagah $- 1$ kabhi use mat karo — yeh har real answer se chhota dikhta hai aur result corrupt kar dega. Agar tum $- 1$ "impossible" signal karna chahte ho, toh usmein convert karo sirf table finish hone ke baad (return dp[amount] if dp[amount] != INF else -1).

State. dp[a] = amount $a$ sum karne ke liye fewest coins. Yeh step kyon? 0 se target tak har amount ke liye ek box.
Sentinel initialisation. Har dp[a] ko INF (jaise upar define kiya) se initialise karo, except dp[0]=0. Yeh step kyon? INF matlab "abhi tak reachable nahi." Kyunki hum min lete hain, ek unreachable path kabhi nahi jeetega.
Recurrence. Har amount $a$ aur coin $c \leq a$ ke liye: $d p [a] = min (d p [a], 1 + d p [a - c]) .$ Yeh step kyon? Ek coin $c$ use karne se ek chhota subproblem $a - c$ bachta hai; 1 add karo us coin ke liye jo humne abhi spend kiya. Agar $d p [a - c]$ abhi bhi INF hai, toh $1 + INF$ effectively INF rehta hai aur min haar jaata hai — impossibility safely propagate hoti hai.
Order. $a$ 1 se target tak. Yeh step kyon? $d p [a - c]$ ki amount chhoti hai, already finalized.
Answer. dp[target], ya "impossible" ( $- 1$ mein convert karo) agar woh abhi bhi INF hai.

Words mein fill karna (coins ${1, 3, 4}$ ):

dp[1]: sirf coin 1 fit hoti hai → $1 + d p [0] = 1$ .
dp[2]: sirf coin 1 fit hoti hai → $1 + d p [1] = 2$ .
dp[3]: coin 1 → $1 + d p [2] = 3$ ; coin 3 → $1 + d p [0] = 1$ ; min $= 1$ .
dp[4]: coin 1 → $1 + d p [3] = 2$ ; coin 3 → $1 + d p [1] = 2$ ; coin 4 → $1 + d p [0] = 1$ ; min $= 1$ .
dp[5]: coin 1 → $1 + d p [4] = 2$ ; coin 3 → $1 + d p [2] = 3$ ; coin 4 → $1 + d p [1] = 2$ ; min $= 2$ .
dp[6]: coin 1 → $1 + d p [5] = 3$ ; coin 3 → $1 + d p [3] = 2$ ; coin 4 → $1 + d p [2] = 3$ ; min $= 2$ .

a	0	1	2	3	4	5	6
dp[a]	0	1	2	1	1	2	2

Toh dp[6] = 2 (coins $3 + 3$ ). Greedy ke 3 se better!

Impossible case: sirf coins ${3, 4}$ ke saath, dp[1] aur dp[2] kabhi reach nahi hote (koi coin $\leq 2$ nahi hai), toh woh INF pe rahte hain — amount 1 ya 2 genuinely unmakeable hai, aur humara sentinel woh cleanly report karta hai bina kisi baad ke min ko corrupt kiye.

Verify: $6 = 3 + 3$ 2 coins use karta hai; koi single coin 6 ke barabar nahi aur koi coin pair 2 se better nahi, toh minimum = 2. Aur ${3, 4}$ ke saath, amount $2$ = impossible. ✅

Ex 5 — C5: order matters (1D space-optimised knapsack)

Forecast: agar hum capacity loop low→high chalayein, kya answer bahut bada hoga ya bahut chhota?

Hum sirf ek row rakhte hain aur use in-place update karte hain. Recurrence ban jaata hai dp[c] = max(dp[c], v_i + dp[c-w_i]), wohi $w_{i}, v_{i}$ use karke (item $i$ ka weight/value) jo Ex 3 mein define kiye. Subtlety: dp[c-w_i] abhi bhi previous item ki value represent karna chahiye, is item ki freshly-updated value nahi (woh same item do baar pick karne deta — 0/1 break hota). (Dekho Space Optimization in DP.)

Figure danger clearly dikhati hai. Cells ki single row hamare dp[c] shelf hai, $c = 0..4$ . Upar yellow arrow safe sweep direction dikhata hai (high→low). Jab hum yellow upd cell dp[4] update karte hain, pink curved arrow dikhata hai ki woh apne left wale blue old cell ko read kar raha hai — aur kyunki hum right se sweep karte hain, woh left cell is round mein abhi overwrite nahi hua, toh woh abhi bhi previous item ki value rakhta hai. Doosri taraf sweep karo aur woh left cell already is-round ki value hogi → item reuse ho jaayegi.

Correct — loop $c$ high→low. Jab hum dp[4] likhte hain, uske left wala cell dp[4-w] abhi bhi last-round ki value hai kyunki is round mein humne usse abhi touch nahi kiya. Yeh step kyon? High→low guarantee karta hai ki read ek not-yet-overwritten (i.e. previous-row) cell se ho.
Wrong — loop $c$ low→high. Hum pehle dp[1] update karenge, phir dp[2] abhi-abhi-updated dp[1] padh sakta hai, effectively ek item reuse karte hue.

Concrete failure item $(1, 1)$ ke saath zeros se start karke, low→high (main har update order mein likhta hoon): dp[1]=max(0,1+dp[0])=1, phir dp[2]=max(0,1+dp[1])=2, phir dp[3]=max(0,1+dp[2])=3, phir dp[4]=max(0,1+dp[3])=4 — item 1 chaar baar use kiya! Yeh unbounded knapsack hai, 0/1 nahi.

Poori item list par high→low sahi 5 deta hai (Ex 3 ke dp[3][4] se match karta hai).

Verify: correct 1D high→low answer = 5 (2D result ke barabar). Buggy low→high ek single item $(1, 1)$ par $W = 4$ ke saath 4 deta hai (galat, item reused). ✅

Ex 6 — C6: do strings, diagonal dependency (LCS)

Forecast: LCS length guess karo — 3, 4, ya 5?

Ek subsequence order rakhta hai lekin letters skip kar sakta hai. Pehle, do strings ka naam rakho taaki recurrence unambiguous ho:

Recurrence mein ek match case aur ek mismatch case hai: $d p [i] [j] = {d p [i - 1] [j - 1] + 1 max (d p [i - 1] [j], d p [i] [j - 1]) X_{i} = Y_{j} (match — diagonal extend karo) X_{i} \neq = Y_{j} (ek letter drop karo)$

Figure teen neighbours dikhati hai jis par har cell depend karta hai. Pink ? cell woh dp[i][j] hai. Ek match par (yellow diagonal arrow) woh up-left cell dp[i-1][j-1] copy karke 1 add karta hai — shared last letter ek common subsequence cap karta hai, baaki strictly-smaller prefixes mein rehta hai. Ek mismatch par (do pink arrows) woh up cell dp[i-1][j] ( $X$ ka last letter drop karo) aur left cell dp[i][j-1] ( $Y$ ka last letter drop karo) mein se bada leta hai.

Ab poori 5-step recipe apply karo:

State. dp[i][j] = $X$ ke pehle $i$ letters aur $Y$ ke pehle $j$ letters ke LCS ki length (jaise upar define kiya).
Recurrence. Upar dikhaye gaye match/mismatch cases. Yeh step kyon? Agar last letters match karte hain toh unhe ek common subsequence ki tail ke roop mein reuse kiya ja sakta hai; agar nahi toh answer do mein se ek last letter ignore karta hai, toh hum dono try karte hain aur better rakhte hain.
Table dimensions & base. $(∣ X ∣ + 1) \times (∣ Y ∣ + 1) = 8 \times 6$ size ki grid dp allocate karo — empty prefix ke liye ek extra row aur column. Row 0 aur column 0 sab zeros se initialise karo. Yeh step kyon? Ek empty string kisi bhi cheez ke saath koi letter share nahi karti, toh uski LCS length 0 hai; aur $i = 1$ ya $j = 1$ par recurrence ko valid row 0 / column 0 padhnee padti hai.
Order. Row by row fill karo (increasing $i$ ), aur har row ke andar left se right (increasing $j$ ). Yeh step kyon? Har cell up (dp[i-1][j]), left (dp[i][j-1]) aur up-left (dp[i-1][j-1]) padhta hai; yeh order guarantee karta hai ki teeno unhe padhne se pehle already fill ho chuke hain.
Answer. Bottom-right cell dp[|X|][|Y|] = dp[7][5]. Yeh step kyon? Woh cell poore $X$ ka poore $Y$ ke against LCS hai.

Yeh hai poori table (rows = $X =$ ABCBDAB ke letters top-to-bottom, columns = $Y =$ BDCAB ke letters left-to-right). Row/col 0 empty-prefix zeros hain.

	B	D	C	A	B
∅	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	2
C	1	1	2	2	2
B	1	1	2	2	3
D	1	2	2	2	3
A	1	2	2	3	3
B	1	2	2	3	4

Kuch cells padho rules fire hote dekhne ke liye:

Row A, col A: letters match karte hain (A=A) → up-left 0 + 1 = 1.
Row B, col B (last column): match (B=B) → up-left cell (row A, col A = 1) + 1 = 2.
Row C, col C: match → up-left (row B, col D = 1) + 1 = 2.
Bottom-right (row B, col B): match → up-left (row A, col A = 3) + 1 = 4.
Ek mismatch example — row B, col D: B≠D → max(up = 0, left = 1) = 1.

Bottom-right cell 4 hai — ek witnessing subsequence "BCAB" hai.

Verify: "BCAB" dono ABCBDAB aur BDCAB mein order mein appear hota hai, aur koi length-5 common subsequence exist nahi karta. LCS length = 4. ✅

Ex 7 — C7: real-world word problem (max non-adjacent loot)

Forecast: do sabse bade, 9 aur 7 pakadna clash hoga (adjacent hain). Real max kya hai?

English constraint "koi do adjacent nahi" har ghar ke liye ek take/skip decision ban jaata hai — pure tabulation. $a_{i}$ matlab "ghar $i$ mein cash" (0-indexed: $a_{0} = 2, a_{1} = 7, a_{2} = 9, a_{3} = 3, a_{4} = 1$ ).

State. dp[i] = houses $0.. i$ consider karte hue max loot. Yeh step kyon? Informal goal ko ek box meaning mein translate karo.
Recurrence. House $i$ jiske paas cash $a_{i}$ hai, ya toh use skip karo (dp[i-1] rakho) ya rob karo ( $a_{i}$ lo plus do houses peeche se best, dp[i-2], kyunki $i - 1$ ab forbidden hai): $d p [i] = max (d p [i - 1], a_{i} + d p [i - 2]) .$ $d p [i - 2]$ kyon? House $i$ robbing karna house $i - 1$ ban karta hai; nearest safe prior state $i - 2$ hai.
Base. dp[0]=a_0=2; dp[1]=max(a_0,a_1)=max(2,7)=7. Yeh step kyon? Ek ya do houses ke saath "two back" recurse karne ke liye kuch nahi hai.
Order. Increasing $i$ ; Answer. dp[4].

Words mein fill karna:

dp[2] $= max (d p [1], a_{2} + d p [0]) = max (7, 9 + 2) = 11$ .
dp[3] $= max (d p [2], a_{3} + d p [1]) = max (11, 3 + 7) = 11$ .
dp[4] $= max (d p [3], a_{4} + d p [2]) = max (11, 1 + 11) = 12$ .

i	0	1	2	3	4
$a_{i}$	2	7	9	3	1
dp[i]	2	7	11	11	12

Verify: houses ${0, 2, 4} = 2 + 9 + 1 = 12$ loot karo. Adjacency avoid karne wala koi bhi set: ${1, 3} = 10$ , ${0, 2} = 11$ , ${2, 4} = 10$ — koi 12 nahi beat karta. Max = 12. ✅

Ex 8 — C8: exam trap (ek galat "obvious" recurrence)

Forecast: {1,2} se 4 ki combinations hain: 1+1+1+1, 1+1+2, 2+2 → 3 ways. Kya student ka formula 3 dega?

Trap, work out karke. Student ka dp[a]=dp[a-1]+dp[a-2] Fibonacci/stairs shape hai — lekin woh ordered sequences count karta hai (woh poochha "kya last piece ek 1 tha ya 2?", jo order distinguish karta hai). Actually dp[0]=1, dp[1]=1 ke saath chalate hain:
- dp[2] $= d p [1] + d p [0] = 1 + 1 = 2$ .
- dp[3] $= d p [2] + d p [1] = 2 + 1 = 3$ .
- dp[4] $= d p [3] + d p [2] = 3 + 2 = 5$ .
Toh student ko 5 milta hai. Woh 5 hain ordered writings 1111, 112, 121, 211, 22 — woh 112, 121, 211 ko teen alag cheezein count karta hai, ek combination "do 1's aur ek 2" ko overcount karta hai. Yeh step kyon? Hume galat number appear hote dekhna hoga taaki fix par trust aaye.
Fix — coin outer loop. Combinations count karne ke liye, coins ko bahar iterate karo, amounts andar:
```
dp = [0]*(amount+1); dp[0] = 1
for c in coins:            # ek coin type ke baare mein ek baar mein decide karo
    for a in range(c, amount+1):
        dp[a] += dp[a-c]
```
Yeh step kyon (zaroori justification)? Coin loop ko bahar rakhne ka matlab hai hum coin 1 ke baare mein saare decisions coin 2 ko kabhi touch karne se pehle finish karte hain. Jab hum coin 2 par move karte hain, hum sirf 1's se already bane amounts ke upar 2's append kar sakte hain — hum kabhi wapas nahi jaate aur 2 ke baad ek 1 interleave nahi karte. Woh fixed processing order (sab 1's, phir sab 2's) har multiset ko exactly ek canonical order mein appear karaata hai, toh 112 vs 121 jaise reorderings kabhi dono count nahi ho sakte. Loops swap karo (amount bahar, coin andar) aur tum phir se har ordering introduce karte — waapis permutations count karne lage.
Trace (coins ${1, 2}$ , amount 4). Coin-1 pass ke baad, har amount ka exactly ek way hai (sab 1's): dp = [1,1,1,1,1]. Ab coin-2 pass dp[a] += dp[a-2] karta hai $a = 2..4$ ke liye:
- dp[2] += dp[0]: $1 + 1 = 2$ .
- dp[3] += dp[1]: $1 + 1 = 2$ .
- dp[4] += dp[2]: $1 + 2 = 3$ .

a	0	1	2	3	4
after coin 1	1	1	1	1	1
after coin 2	1	1	2	2	3

Answer. dp[4] = 3 — hamare hand count {1111, 112, 22} se match karta hai.

Verify: {1,2} se 4 ki combinations = {1111,112,22} = 3; naive stairs recurrence 5 tak overcount karta hai. ✅

Recall Koi bhi tabulation code karne se pehle scenario checklist

Kya maine degenerate input (empty / zero) handle kiya? (Ex 2)
Kya koi state "impossible" matlab rakhti hai — aur kya mera sentinel min/max-safe hai? (Ex 4)
Kya meri loop direction in-place / 1D collapse ke liye sahi hai? (Ex 5)
Kya main order count kar raha hoon ya combinations — kya loop nesting sahi hai? (Ex 8)

Active recall

Tribonacci base cases — tumhe kitne chahiye aur kyon?

Teen (dp[0],dp[1],dp[2]) kyunki recurrence 3 steps peeche jaati hai; kam hone par negative index padha jaata.

Climbing-stairs / counting DP mein dp[0]=1 (0 nahi) kyon?

Moves ka empty sequence ek valid way hai; 0 use karna downstream sums tod deta.

Coin Change min-coins mein, unreachable cells ko ∞ se initialise kyon karein, −1 se nahi?

Taaki min() kabhi galat se ek impossible path na choose kare; −1 chhota dikhta hai aur min corrupt kar deta hai.

1D 0/1 knapsack: kaunsi capacity loop direction aur kyon?

High→low, taaki dp[c−w] abhi bhi previous item ki value rakhe (koi reuse nahi).

LCS match vs mismatch recurrence?

Match: dp[i−1][j−1]+1; mismatch: max(dp[i−1][j], dp[i][j−1]).

LCS table dimensions aur base?

Size (|X|+1)×(|Y|+1); row 0 aur column 0 sab zeros (empty prefix kuch share nahi karta).

House robber recurrence?

dp[i]=max(dp[i−1], a_i+dp[i−2]); house i rob karna i−1 forbid karta hai toh hum i−2 par fall back karte hain.

Coin Change: ordered count vs combination count — kya badalta hai?

Combination count coin loop ko amount loop ke BAHAR rakhta hai; ordered count amount ko bahar rakhta hai.

Connections

Tabulation (bottom-up DP) — iterative (index 3.7.8) — woh parent recipe jise yeh examples exercise karte hain
0-1 Knapsack, Coin Change, Longest Common Subsequence — yahan trace ki gayi classic tables
Space Optimization in DP — Ex 5 ka 1D collapse
Recurrence Relations — har recurrence kahan se aati hai
Optimal Substructure, Overlapping Subproblems — kyon har example kaam karta hai
Memoization (top-down DP) — top-down twin