Dynamic programming — overlapping subproblems, optimal substructure: Worked examples

3.7.6 · D3 · Coding › Algorithm Paradigms › Dynamic programming — overlapping subproblems, optimal subst

Yeh page Dynamic Programming ka exhaustive drill room hai. Parent note ne tumhe idea diya. Yahan hum har tarah ke case walk through karte hain jo ek DP problem tumhare saamne throw kar sakti hai — taaki jab exam ya interview mein koi weird corner aaye, tum uska twin pehle se dekh chuke ho.

Pehli line se pehle: DP ka matlab hai "recursion + answers yaad rakhna"; ek subproblem original question ka ek chota version hota hai (jaise $F (5)$ ke andar $F (3)$ ); ek recurrence wo formula hai jo chote answers se bada answer banata hai; ek base case sabse chota subproblem hai jiska answer hum bina recurse kiye seedha jaante hain. Neeche har symbol in char words pe bana hai.

The scenario matrix

Har DP problem in case classes mein se kisi ek mein aati hai. Neeche ke examples labeled hain ki wo kaun sa cell hit karte hain. Agar tum har cell solve kar sako, toh koi bhi DP problem tumhe surprise nahi kar sakti.

#	Case class	Kya cheez tricky banati hai	Example jo isse cover karta hai
C1	1-D DP, tiny base	sahi base case choose karna	Ex 1 — edge pe Fibonacci
C2	Degenerate / zero input	$n = 0$ , empty array, capacity 0	Ex 2 — Knapsack with $W = 0$
C3	2-D DP grid	do indices saath move karte hain	Ex 3 — Longest Common Subsequence
C4	"Take vs skip" choice	har item pe ek decision	Ex 4 — Knapsack full trace
C5	Overlap present, substructure ABSENT	DP galat answer deta hai	Ex 5 — Longest simple path trap
C6	Overlap ABSENT	DP memory waste karta hai, koi speedup nahi	Ex 6 — Merge Sort
C7	Real-world word problem	prose → recurrence translate karna	Ex 7 — Coin change (fewest coins)
C8	Negative values / limiting behaviour	signs aur $\infty$ sentinels	Ex 8 — Bellman-Ford relaxation
C9	Exam twist: wrong fill order	bug dhundho	Ex 9 — Broken tabulation

Ex 1 — C1: 1-D DP, tiny base case

Forecast: $F (6)$ ki value guess karo aur bottom-up kitne additions leta hai — yeh aage padhne se pehle socho.

Figure — Dynamic programming — overlapping subproblems, optimal substructure

Base cells likho. $d p [0] = 0$ , $d p [1] = 1$ . Yeh step kyun? Recurrence $F (n) = F (n - 1) + F (n - 2)$ do steps neeche jaati hai, isliye koi bhi loop shuru hone se pehle hume do sabse chote values pata hone chahiye. Dono bases ke bina, $d p [2]$ ke paas padhne ko kuch nahi hoga.
Upar ki taraf fill karo $i = 2 \dots 6$ (figure mein green arrows dekho, har cell apne left ke do cells se pull karta hai): $d p [2] = 1, d p [3] = 2, d p [4] = 3, d p [5] = 5, d p [6] = 8$ . Yeh step kyun? Increasing $i$ mein fill karna guarantee karta hai ki $d p [i - 1]$ aur $d p [i - 2]$ pehle se computed hain — yahi optimal substructure ek loop order mein convert hota hai.
Additions count karo. Har naye cell ke liye ek addition, cells $2$ se $6$ tak = 5 additions. Yeh step kyun? Complexity $= (# subproblems) \times (work each)$ ; yahan $\approx n$ subproblems $\times O (1)$ .

Verify: $F (6) = 8$ classic sequence $0, 1, 1, 2, 3, 5, 8$ se match karta hai. Naive recursion $F (6)$ se $\approx 25$ calls spawn karta — hamare 5 additions $O (2^{n}) \to O (n)$ collapse confirm karte hain.

Ex 2 — C2: degenerate zero input

Forecast: Kya algorithm crash karega, ya kuch sensible return karega?

Capacity 0 case. Recurrence ki "take" branch ko $w_{i} \leq c$ chahiye. $c = 0$ aur har $w_{i} \geq 1$ ke saath, woh branch kabhi allowed nahi hoti, isliye $K (i, 0) = K (i - 1, 0) = \dots = 0$ . Yeh step kyun? Hume dikhana hai ki recurrence ka guard clause $w_{i} > c$ boundary handle karta hai — koi item fit nahi hota, toh value 0 rehti hai.
Zero items case. Base row $K (0, c) = 0$ sab $c$ ke liye. Yeh step kyun? Pack karne ke liye kuch nahi hai, toh optimum trivially 0 hai regardless of capacity. Degenerate inputs poori tarah base case mein rehte hain.

Verify: Dono answers $0$ hain. Sanity check: value negative nahi ho sakti aur koi item kabhi place nahi hua, isliye 0 hi ek possible packed value hai. Units: value "value points" mein rehti hai, capacity "weight units" mein — koi unit mixing nahi hua.

Ex 3 — C3: 2-D DP grid (LCS)

Forecast: Length guess karo. (Ek subsequence order rakhta hai lekin letters drop kar sakta hai.)

$L (i, j)$ = string $X$ ke pehle $i$ letters aur string $Y$ ke pehle $j$ letters ka LCS length.

Base cells. $L (0, j) = L (i, 0) = 0$ : ek empty prefix kuch share nahi karta. Yeh step kyun? Do indices $\Rightarrow$ ek 2-D table; base poori pehli row aur column hai (empty-string cases).
Recurrence. Agar letters match hote hain, diagonal extend karo: $L (i, j) = {L (i - 1, j - 1) + 1 max (L (i - 1, j), L (i, j - 1)) X_{i} = Y_{j} X_{i} \neq = Y_{j}$ Yeh step kyun? Match ka matlab hai dono strings ne same letter gain kiya — optimal answer mein yeh zaroor include hoga (optimal substructure), isliye hum diagonally jump karte hain aur 1 add karte hain. Mismatch ka matlab hai hum ek string se ek letter drop karte hain aur dono mein se better lete hain.
Grid fill karo row by row (figure mein blue diagonal arrows "+1 on match" moves hain). Bottom-right cell answer hai: 4 ("BCAB"). Yeh step kyun? Har $(i, j)$ sirf upar/left/diagonal cells padhta hai — sab pehle fill ho chuke hain — isliye left-to-right, top-to-bottom har dependency respect karta hai.

Verify: "BCAB" length 4 hai, dono A**B**C**B**D**A****B** aur **B**D**C****A****B** mein order mein appear karta hai. Koi length-5 common subsequence exist nahi karta. Answer $= 4$ . ✓

Ex 4 — C4: full "take vs skip" trace

Forecast: Greedy-by-ratio item 1 (ratio 1) grab karega, phir item 2 (ratio 1.33)… guess karo kya greedy yahan sahi answer bhi deta hai.

Recurrence (parent se): $K (i, c) = max (K (i - 1, c), v_{i} + K (i - 1, c - w_{i}))$ jab $w_{i} \leq c$ . Yeh step kyun? Har item pe hum ya toh skip karte hain (value $K (i - 1, c)$ ) ya take karte hain (gain $v_{i}$ , capacity shrink hoti hai). Optimal substructure guarantee karta hai ki do optimal sub-answers mein se best overall optimal hoga.
Items 2 aur 4 lene ki koshish ( $w = 3 + 5 = 8 > 7$ ) — bahut heavy, blocked. Yeh step kyun? Guard $w_{i} \leq c$ infeasible combos prune karta hai; hume har branch pe capacity respect karni hogi.
Best feasible combo: items 2 aur 3 ( $w = 3 + 4 = 7 = W$ , $v = 4 + 5 = 9$ ). Yeh step kyun? Hum item 1+3 ( $w = 5$ , $v = 6$ ), item 4 akela ( $v = 7$ ), item 2+3 ( $v = 9$ ) se compare karte hain — DP table quietly inhe sab check karta hai aur max rakhta hai.

Verify: $K (4, 7) = 9$ . Greedy trap check karo: greedy by ratio ( $1, 1.33, 1.25, 1.4$ ) item 4 pehle grab karta hai (ratio 1.4, value 7, weight 5), phir sirf item 1 fit hota hai (weight 6, value 8) — greedy score 8 < 9. Yahi "greedy fails 0/1" galti hai. DP jeetta hai. ✓

Ex 5 — C5: overlap present lekin NO optimal substructure

Forecast: DP chalta hai aur ek number return karta hai — kya woh sahi hoga?

Naive substructure claim try karo: "D tak longest simple path = C tak longest simple path, phir C→D." Yeh step kyun? Hum test karte hain ki kya poora optimum sub-optima se bana hai — yahi optimal substructure ki definition hai.
Counterexample dhundho. C tak longest simple path A→B→C ho sakta hai (B use karta hai). Lekin C ke zariye D tak longest simple path ke liye ek alag route ke liye B avoid karna pad sakta hai — sub-answer "best path to C" bhool jaata hai ki usne kaun se vertices already use kiye. Yeh step kyun? Simple paths revisiting forbid karte hain, isliye ek cached sub-answer sirf ek specific set of used vertices ke liye valid hai — cache key (node) incomplete hai.
Conclusion: sirf node pe memoizing karna galat answer deta hai, chahe subproblems overlap karein. Yeh step kyun? Overlap caching ko tempting banata hai; missing optimal substructure use incorrect banata hai. Pehle substructure prove karna zaroori hai.

Verify: Yahan true longest simple A→D path A→B→C→D hai (length 3 edges). Sirf node pe keyed naive memo ise shorter A→C→D (length 2) se distinguish nahi kar sakta, isliye yeh galat path return kar sakta hai — yeh failure demonstrate karta hai. (Longest-simple-path isi wajah se NP-hard hai.) ✓

Ex 6 — C6: overlap ABSENT — DP pointless hai

Forecast: Kya cache kabhi hit lega?

Subproblems list karo: sort [5,2,8,1] → sort [5,2] aur [8,1] → sort [5],[2],[8],[1]. Yeh step kyun? Hum repeats check karne ke liye enumerate karte hain — cache sirf yahi exploit karta hai.
Overlap check karo: har sub-array ek distinct slice hai. Koi bhi do recursive calls same question nahi poochte. Yeh step kyun? Koi repeat nahi ⇒ koi cache hit nahi ⇒ zero time saved, sirf memory waste.

Verify: Merge Sort $O (n lo g n)$ hai bina kisi DP ke; $O (n)$ size ka cache all-distinct inputs pe 0 hits dega. Parent ka "har recursion ko DP nahi karna chahiye" confirm hota hai. Disjoint tree visualise karne ke liye Recursion Trees dekho. ✓

Ex 7 — C7: real-world word problem (coin change)

Forecast: Greedy sabse bada coin pehle lega (4, phir 1, phir 1 = 3 coins). Kya greedy optimal hai?

Subproblem define karo. $M (a)$ = amount $a$ banane ke liye fewest coins. Base: $M (0) = 0$ . Yeh step kyun? Prose ko recurrence mein translate karna: "make $a$ " ek coin use karne ke baad "make $a - coin$ " mein shrink ho jaata hai.
Recurrence. $M (a) = 1 + min_{coin c \leq a} M (a - c)$ . Yeh step kyun? Ek coin $c$ use karne se amount $a - c$ bachta hai; best overall hai 1 (yeh coin) plus baaki banane ka best tarika — optimal substructure hold karta hai kyunki sub-amounts "interfere" nahi karte.
Fill up $a = 1 \dots 6$ : $M (1) = 1, M (2) = 2, M (3) = 1, M (4) = 1, M (5) = 2, M (6) = 2$ (coins $3 + 3$ ). Yeh step kyun? Bottom-up taaki har $M (a - c)$ use padhne se pehle ready ho.

Verify: $M (6) = 2$ ( $3 + 3$ use karke). Greedy ne 3 score kiya ( $4 + 1 + 1$ ) — greedy yahan galat hai, DP sahi hai. Sanity: $3 + 3 = 6$ ✓, aur koi single coin 6 ke barabar nahi, isliye 2 minimal hai. ✓

Ex 8 — C8: negative weights & limiting sentinels (Bellman-Ford)

Forecast: Negative edge ko dekhte hue, direct edge (5) jeetta hai ya detour through A?

Initialise karo. $d i s t [S] = 0$ , baaki sab $= + \infty$ . Yeh step kyun? $+ \infty$ sentinel hai jiska matlab hai "unreached." Relaxation sirf finite-ya-infinite estimates ko neeche improve karta hai.
Har edge relax karo (DP update $d i s t [y] = min (d i s t [y], d i s t [x] + w)$ ): S→A: $d i s t [A] = 0 + 4 = 4$ . A→T: $d i s t [T] = 4 + (- 2) = 2$ . S→T: $min (2, 0 + 5) = 2$ . Yeh step kyun? Har relaxation ek "is edge lo vs current best rakho" choice hai — same take/skip pattern jaise knapsack, lekin minimising ke saath aur negative edge weights allow karta hai.
Limiting note. Agar koi negative cycle hoti, distances kisi bhi bound se neeche girate rehte — Bellman-Ford ise $∣ V ∣ - 1$ baar relax karke phir ek aur pass check karke detect karta hai. Yeh step kyun? Degenerate "koi finite optimum nahi" case cover karna.

Verify: $d i s t [T] = 2$ via S→A→T ( $4 - 2 = 2$ ), direct 5 ko beat karta hai. Negative edge ka handling sahi hai. ✓

Ex 9 — C9: exam twist — broken fill order dhundho

Worked example Statement

Yeh tabulation Fibonacci compute karne ki koshish karta hai lekin garbage return karta hai. Bug dhundho.

def fib(n):
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(n, 1, -1):        # ← suspicious
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Forecast: Kaun si line dependency direction violate karti hai?

Recurrence ki dependency padho: $d p [i]$ ko $d p [i - 1]$ aur $d p [i - 2]$ chahiye — chote indices. Yeh step kyun? Tabulation ka iron rule: kisi index ko tabhi fill karo jab woh sab kuch jo woh padhta hai fill ho chuka ho.
Loop inspect karo: range(n, 1, -1) $n$ se neeche count karta hai. Toh $d p [n]$ pehle compute hota hai, $d p [n - 1]$ aur $d p [n - 2]$ padhte hue — dono abhi 0 hain. Yeh step kyun? Un-filled cells (sab zero) padhna exactly wahi "wrong fill order" galti hai jo parent note mein thi.
Fix: upar iterate karo: for i in range(2, n+1). Yeh step kyun? Increasing order guarantee karta hai ki dependencies ready hain — Ex 1 se match karta hai.

Verify: Buggy downward loop aur $n = 6$ ke saath, har read zeros hit karti hai, toh $d p [6] = 0 + 0 = 0$ — galat. Fixed upward loop $d p [6] = 8$ deta hai (Ex 1). ✓

Recall Kaun sa cell sabse mushkil tha?

Kaun sa case DP ko galat (sirf slow nahi) answer return karwata hai? ::: C5 — overlap present lekin koi optimal substructure nahi (longest simple path). Kaun sa case DP ko memory ka waste banata hai bina kisi speedup ke? ::: C6 — koi overlapping subproblems nahi (Merge Sort). Coin change mein {1,3,4} coins se 6 banane ke liye greedy kyun fail karta hai? ::: Greedy 4+1+1=3 coins leta hai, lekin 3+3=2 coins optimal hai; greedy-choice property hold nahi karti.

Connections

Parent: DP topic note
Recursion · Recursion Trees — in examples jo trees collapse karte hain.
Memoization vs Tabulation — top-down vs bottom-up, Ex 1 & 9 mein dekha gaya.
Knapsack Problem · Longest Common Subsequence · Bellman-Ford — teen canonical DPs jo upar drill hue.
Divide and Conquer — Ex 6 ka disjoint contrast. · Greedy Algorithms — Ex 4 & 7 ka failed shortcut.
Time Complexity Analysis — $O (n)$ , $O (nW)$ counts.