Exercises — Dynamic programming — overlapping subproblems, optimal substructure

(a) Fibonacci — dono. $F(n)$ ka call tree chhote $k$ ke liye $F(k)$ ko bahut zyada baar recompute karta hai → overlap. Aur $F(n)=F(n-1)+F(n-2)$ literally sub-answers se answer banata hai → optimal substructure. ✅ DP apply hoti hai. (b) Merge Sort — sirf optimal substructure. Poore array ko sort karna dono halves ko sort karne se banta hai, toh substructure hai. Lekin dono halves disjoint index ranges hain — koi bhi subproblem dobara nahi aata, toh koi overlap nahi hai. ⇒ Ye Divide and Conquer hai, DP nahi. Caching yahan zero speedup ke liye memory waste karega. (c) Scanning se Max — kuch bhi nahi (trivially). Ek linear pass hai; koi recursion kuch bhi revisit nahi karta. Cache karne ke liye kuch nahi hai.

Nahi. DP ko optimal substructure chahiye. Longest simple path ke liye ye fail hoti hai: $s\to t$ ka best path nahi banta ek independently-best $s\to m$ plus best $m\to t$ se, kyunki woh pieces vertices reuse kar sakti hain, jo "simple" forbid karta hai. Sub-answers composable nahi hain, toh unhe cache karna galat results deta hai. (Ye bilkul wahi warning hai jo parent note mein hai: memoize karne se pehle substructure prove karo.)

Sabse chhote se bade tak fill karo taaki har entry ki dependencies pehle se exist karein: $0,1,1,2,3,5,8,13$ indices $\mathrm{0..7}$ ke liye. Toh $F(7)=13$. Har cell ne sirf $dp[i-1]+dp[i-2]$ use kiya — dono pehle se likhe hue the. Ye optimal substructure concrete form mein hai.

Rows = items considered $\mathrm{0..4}$, columns = capacity $c=\mathrm{0..5}$. Row $0$ sab zeros hai (koi item nahi). Figure ki grid padhke:

Sample cell $K(2,5)$: $B$ skip karo → $K(1,5)=3$; $B$ lo → $4+K(1,5-3)=4+K(1,2)=4+3=7$. Max $=7$. Answer: $7$ ($A+B$ lo: weight $2+3=5\le 5$, value $3+4=7$). $C,D$ yahan last column improve nahi karte.

$dp[0]=0$. $a\ge 1$ ke liye, $dp[a]=1+{\min }_{\text{coin }k\le a}dp[a-k]$.

• $dp[1]=1+dp[0]=1$
• $dp[2]=1+dp[1]=2$
• $dp[3]=\min (1+dp[2],1+dp[0])=\min (3,1)=1$
• $dp[4]=\min (1+dp[3],1+dp[1],1+dp[0])=\min (2,2,1)=1$
• $dp[5]=\min (1+dp[4],1+dp[2],1+dp[1])=\min (2,3,2)=2$
• $dp[6]=\min (1+dp[5],1+dp[3],1+dp[2])=\min (3,2,3)=2$

Answer: $dp[6]=2$ (coins $3+3$).

Naive: har node do children spawn karta hai, aur koi memory nahi hai, toh tree roughly har level par double hoti hai → lagbhag $2^n$ nodes, har ek $O(1)$ kaam karta hai ⇒ $O(2^n)$. Figure ki left tree mein $F(3)$ do baar, $F(2)$ teen baar aata hai — pure repeated kaam. Memoized: pehli baar jab bhi $F(k)$ compute hota hai, cache fill ho jaata hai; baad mein har request $O(1)$ lookup hai (right tree mein greyed nodes). Sirf $n+1$ distinct values $F(\mathrm{0..}n)$ hain, har ek ek baar compute hota hai ⇒ parent ka formula use karke $\text{Time}=(\#\text{distinct subproblems})\times (\text{work each})=(n+1)\times O(1)=O(n).$

$O(nW)$ pseudo-polynomial hai, truly polynomial nahi. $W$ ek value hai, aur bits mein iski size ${\log }_{2}W$ hai, toh table mein $n\cdot W$ cells hain lekin input sirf $\sim n\log W$ bits ka hai. Yahan $n\cdot W=5\times 10^{10}$ cells hain — infeasible, chahe $n$ kitna bhi chhota ho. $n$ mein fast hai, $W$ ke bits mein exponential hai. (Dekho Time Complexity Analysis.)

Maano $d_k(v)=$ $v$ tak at most $k$ edges use karke shortest distance. Optimal substructure: $v$ tak $\le k$-edge shortest path kisi neighbour $u$ tak $\le (k-1)$-edge shortest path hai, plus edge $u\to v$: $d_k(v)=\min (d_{k-1}(v),{\min }_{u\to v}(d_{k-1}(u)+w(u,v)\left)\right).$ Ek simple shortest path at most $V-1$ edges use karta hai, toh $V-1$ full relaxation rounds ke baad har $d_{V-1}(v)$ final hai. Har round ek DP layer hai; overlap bahut bada hai kyunki kaafi edges same vertex ko feed karte hain. Ye bilkul (#subproblems)$\times$(work) $=O(V)\times O(E)=O(VE)$ hai.

Derivation. Last characters $X_i,Y_j$ dekho.

• Agar $X_i=Y_j$: woh char zaroor chhote prefixes ke LCS ko extend karega, toh $L(i,j)=1+L(i-1,j-1)$.
• Agar $X_i\ne Y_j$: unme se kam se kam ek common subsequence mein nahi hai, toh $L(i,j)=\max (L(i-1,j),L(i,j-1))$.
• Base: $L(0,j)=L(i,0)=0$ (empty prefix).

Optimal substructure: prefixes ka ek optimal LCS chhote prefixes ke optimal LCS se bana hai (swap-in argument). Overlap: $(i-1,j)$ aur $(i,j-1)$ dono $(i-1,j-1)$ mein recurse karte hain — shared subproblems har jagah hain.

Compute $X=$AGCAT (rows), $Y=$GAC (cols). Table $L$ (rows $i=\mathrm{0..5}$, cols $j=\mathrm{0..3}$):

LCS length $=2$ (jaise "AC" ya "GA").

Last move step $n-1$, $n-2$, ya $n-3$ se aaya tha. Ye disjoint final moves hain, toh hum counts add karte hain: $W(n)=W(n-1)+W(n-2)+W(n-3),W(0)=1,W(1)=1,W(2)=2.$

• $W(3)=1+1+2=4$
• $W(4)=2+4+...=W(3)+W(2)+W(1)=4+2+1=7$
• $W(5)=W(4)+W(3)+W(2)=7+4+2=13$

Answer: $W(5)=13$. Optimal substructure = "koi bhi poora tarika exactly ek last hop se khatam hota hai"; overlap = har $W(k)$ teen parents dwara reuse hota hai.

Har row $i$ sirf row $i-1$ padhta hai. Toh ek single 1-D array dp[0..W] rakho aur har item ke liye in-place update karo. Lekin $K(i,c)$ ko $K(i-1,c-w_i)$ chahiye — apni left mein ek entry aur old row se. Agar $c$ upar ki taraf iterate karo, toh dp[c-w_i] ko new row se overwrite kar doge padhne se pehle (isse ek item do baar liya ja sakta hai — unbounded knapsack). 0/1 ke liye old left value preserve karne ke liye, $c$ ko neche ki taraf $W$ se $w_i$ tak iterate karo:

for i in range(n):
    for c in range(W, w[i]-1, -1):
        dp[c] = max(dp[c], v[i] + dp[c-w[i]])

Rule: $c$ ko descend karo taaki har item at most ek baar use ho. Same $O(nW)$ time, ab $O(W)$ space.

Optimal substructure tooti unki state ke relative mein. Jab "har element ≤ do baar use karo" add hota hai, toh index $i$ par answer sirf $i$ par nahi balki itni baar har value pehle se use ho chuki hai — us extra history par depend karta hai — woh true subproblem ka hissa hai. Sirf $i$ par memoize karne se woh states merge ho jaati hain jo actually alag hain, toh ek cached value ek aisi context mein serve hoti hai jahan wo valid nahi hai. Fix: state ko enlarge karo taaki future jo bhi depend karta hai woh sab capture ho (yahan remaining usage budget), ya prove karo ki reduced state sufficient hai. Ek sahi memo key subproblem ko self-contained banana chahiye.

Fractional version ke liye, greedy optimal hai aur DP se simpler hai: value/weight ratio se sort karo aur fill karo. Ratios: $A=3/2=1.5$, $B=4/3\approx 1.33$, $C=5/4=1.25$, $D=6/5=1.2$. $A$ puri lo (2 use, value 3, bachi 3), phir $B$ puri lo (3 use, value 4, bachi 0). Total weight $=5$, value $=7$. Yahan ye 0/1 answer se tie karta hai, lekin generally fractional greedy $\ge$ 0/1 DP. Lesson: DP hamesha sahi hammer nahi hai — jab greedy-choice property hold kare, greedy dono correct bhi hai aur sasta bhi.

Kaun si property DP ko correct banati hai, aur kaun si ise worth it banati hai? Correct ::: Optimal substructure (sub-answers true optimum mein compose hote hain). Worth it ::: Overlapping subproblems (same sub-answer reuse hota hai, toh caching kaam bachata hai).