Exercises — Tabulation (bottom-up DP) — iterative

Rule kehta hai har box = usse pehle ke do boxes ka sum. KYA karte hain: dp[5] aur dp[4] add karo. KYU: recurrence dp[6]=dp[5]+dp[4] — dono pehle se filled hain, isliye hum inhe read kar sakte hain. $dp[6]=5+3=\boxed{8}.$

Bade se start karke neechey recurse karna = memoization (top-down). Dekho Memoization (top-down DP). Tabulation iska ulta hai: sabse chhote boxes se start karo aur loop karke upar jao. Dono har subproblem ko ek baar compute karte hain; sirf travel direction alag hoti hai.

Answer cell: sabse bada state, dp[4]. Base cases: dp[0]=1 (ek tarika — khade raho) aur dp[1]=1 (ek tarika — ek 1-step). Upar fill karte hue: dp[2]=2, dp[3]=3, dp[4]=5.

Seed: dp[0]=0, dp[1]=1. Loop small→large, har box = pichle do ka sum:

$dp[7]=dp[6]+dp[5]=8+5=\boxed{13}.$

State: dp[a] = a summing karne wale combinations ki count. Base: dp[0]=1 (0 banane ka ek tarika — kuch mat lo). KYU coins bahar: combinations (permutations nahi) count karne ke liye, humein ek coin denomination ko poori tarah commit karna hoga next se pehle, taaki {1,2} aur {2,1} double-count na ho.

Start dp = [1,0,0,0,0,0].

Coin 1 process karo (har amount ko a-1 se ways milte hain): dp = [1,1,1,1,1,1]. Coin 2 process karo (har a≥2 ko a-2 se ways milte hain):

• dp[2]+=dp[0]=1 → 2
• dp[3]+=dp[1]=1 → 2
• dp[4]+=dp[2]=2 → 3
• dp[5]+=dp[3]=2 → 3

Final dp = [1,1,2,2,3,3], isliye $\boxed{dp[5]=3}$. Teen tarike: 1+1+1+1+1, 1+1+1+2, 1+2+2. ✅

Recurrence: har coin ko aakhri use kiya hua maano: $dp[i]=1+{\min }_{\text{coin}\le i}dp[i-\text{coin}],dp[0]=0.$ KYU min, sum nahi: yahan hum ek quantity optimize kar rahe hain (fewest coins), isliye best last choice chunte hain — contrast karo L2.2 se jahan hum count karte hain aur isliye add karte hain.

Upar build karo:

dp[6] check karo: candidates 1+dp[5]=3, 1+dp[3]=2, 1+dp[2]=3. Minimum hai $\boxed{2}$ (yani 3+3).

Rows = consider kiye gaye items (0 = koi nahi); columns = capacity c 0 se 4 tak. Row 0 sab zeros hai (koi item nahi → koi value nahi).

Row 1 — item (1,1): c≥1 par le sakte hain. dp[1][c]=max(0, 1+dp[0][c-1])=1. [0, 1, 1, 1, 1]

Row 2 — item (3,4): jab c≥3 ho tab le sakte hain.

• c=0,1,2: bahut heavy → upar se copy karo → 0,1,1
• c=3: max(dp[1][3]=1, 4+dp[1][0]=4)=4
• c=4: max(dp[1][4]=1, 4+dp[1][1]=5)=5 [0, 1, 1, 4, 5]

Row 3 — item (4,5): sirf c=4 par le sakte hain.

• c=0..3: upar se copy karo → 0,1,1,4
• c=4: max(dp[2][4]=5, 5+dp[2][0]=5)=5 [0, 1, 1, 4, 5]

$\boxed{dp[3][4]=5.}$ Do optimal packings value 5 par tie karte hain: sirf item 3, ya items 1+2 (1+4).

Har entry dp[i][c] row i-1 padhta hai. Agar hum pehle row n fill karein, row n-1 abhi bhi sab zeros hai → hum garbage read karte hain. KYA toot ta hai: dependencies read ki jaati hain pehle unke exist karne se. Rule: iterate karo taaki har cell ke inputs pehle se filled hon. Kyunki dp[i] depends karta hai dp[i-1] par, humein small i → large i jaana hoga. Order recurrence ke arrows se dictate hota hai, taste se nahi.

Sahi: high→low. Dekho Space Optimization in DP.

1D update hai dp[c] = max(dp[c], v + dp[c-w]), jahan dp[c-w] ka matlab previous row hona chahiye (item abhi use nahi hua).

Low→high (GALAT): start karo dp=[0,0,0,0,0], item (2,3).

• c=2: dp[2]=max(0,3+dp[0])=3
• c=4: dp[4]=max(0,3+dp[2])=3+3=6 ← item do baar use hua! (unbounded, 0/1 nahi)

High→low (SAHI):

• c=4: dp[4]=max(0,3+dp[2]=3+0)=3
• c=2: dp[2]=max(0,3+dp[0])=3
• final dp=[0,0,3,0,3] → best value 3, item ek baar use hua. ✅

High→low jaana guarantee karta hai ki dp[c-w] is round mein abhi overwrite nahi hua, isliye woh abhi bhi previous row hold karta hai.

State: dp[i][j] = A[0..i) aur B[0..j) ki LCS length. Base: dp[0][j]=dp[i][0]=0 (empty string kuch share nahi karta). Recurrence: $dp[i][j]=\{\begin{array}{ll}dp[i-1][j-1]+1& A_i=B_j(\text{matched letter extends the LCS})\\ \max (dp[i-1][j],dp[i][j-1])& A_i\ne B_j(\text{drop one letter, keep the better side})\end{array}$ KYU: agar aakhri letters match karte hain, toh woh ek common subsequence end kar sakte hain, isliye hum unse pehle ki sab cheez ki LCS lete hain aur 1 add karte hain. Agar nahi milte, toh do aakhri letters mein se kam se kam ek unused hai → dono drop karke dekho aur bada rakho.

Grid fill karte hue (rows = A ke letters, cols = B ke letters), final cell hai: $\boxed{dp[7][5]=4.}$ Length 4 ka ek aisa LCS hai "BCAB" (ya "BDAB").

State: dp[i] = no-two-adjacent rule ke under houses 0..i use karke best total. Recurrence: house i ke liye, ya toh use skip karo (dp[i-1]) ya use lo (cost[i] + dp[i-2], kyunki i-1 ab forbidden hai): $dp[i]=\max (dp[i-1],cost[i]+dp[i-2]).$ Base: dp[0]=cost[0]=2, dp[1]=max(cost[0],cost[1])=7.

• dp[2]=max(7, 9+2)=11
• dp[3]=max(11, 3+7)=11
• dp[4]=max(11, 1+11)=12

$\boxed{dp[4]=12}(\text{houses }2+7+\dots \text{ actually }2+9+1=12).$

Bug: unhone har cell ko 0 se initialise kiya, lekin sirf dp[0] hi 0 hona chahiye. Har doosri cell ko "impossible" = ek bada sentinel se start karna chahiye (jaise amount+1 ya float('inf')). Kyun sahi lagta hai: 0 natural empty value hai aur sahi dp[0] se match karta hai. Kya toot ta hai: recurrence dp[i]=1+min(dp[i-coin]) dusre cells padhta hai; agar woh 0 hain, toh min galat maanta hai ki koi bhi amount almost bina coins ke reachable hai, sab kuch poison karte hue. Fix: $dp=[0,\infty ,\infty ,\dots ],dp[0]=0.$ Ek cell jo end mein bhi ∞ hai matlab "amount unreachable". Base cases table ko seed karte hain; ek galat seed utna hi fatal hai jitna ek missing ek.

Naive recursion alag call paths se ek hi subproblem mein baar baar enter karta hai (Overlapping Subproblems property), isliye F(n) $O({\phi }^n)$ calls spawn kar sakta hai. Tabulation har cell ko single loop pass mein visit karta hai. Formally: outer loop index apni range mein har value ek baar leta hai; har cell exactly ek baar written hoti hai (apni loop iteration mein) aur uske baad sirf read hoti hai. Kyunki hum loop is tarah order karte hain ki dependencies cell se pehle aayein (Optimal Substructure guarantee karta hai ki dependencies chhote states hain), koi bhi cell dubara compute karne ke liye revisit nahi hoti. Result: total work = (cells ki count) × (har cell ki cost). Fibonacci ke liye woh $O(n)$ hai vs exponential recursion.

Rule: Iterate karo taaki har cell jo tum ek update ke dauran read karte ho, intended prior stage ki value hold kare — koi aisi value nahi jo is pass mein pehle se overwrite ho chuki ho.

• Agar reads strictly earlier, never-overwritten cells reference karte hain (rolling vars ke saath Fibonacci) → direction free hai.
• Agar ek read dp[c-w] aur write dp[c] us same array mein hain jo is round mein overwrite ho raha hai, woh direction choose karo jo read location ko write location ke baad visit kare, taaki read abhi bhi purani value dekhe. Knapsack ke liye, c-w < c, isliye high→low likhna dp[c-w] ko baad tak untouched rakhta hai. ✅

Ye exactly Space Optimization in DP safety condition hai, aur ye parent note ki har galti ko cover karta hai.

Yahan har problem wahi chaar moves thi: box ka naam batao (state), fill rule likho (recurrence), woh boxes haath se fill karo jahan koi rule nahi pahunchi (base), aur loop karo taaki ek box ke ingredients use karne se pehle ready hon (order). Counting problems add karte hain; best/least problems min/max lete hain; in-place tricks loop direction se jeeti ya harti hain. Yahi poora ladder hai.