Exercises — DP problems — matrix chain multiplication

Rule hai "$A_i$ mein $p_{i-1}$ aur $p_i$ use hote hain". Array ko overlapping pairs mein walk karo:

• $A_1=p_0\times p_1=5\times 4$
• $A_2=p_1\times p_2=4\times 6$
• $A_3=p_2\times p_3=6\times 2$
• $A_4=p_3\times p_4=2\times 7$

Ye kyon kaam karta hai: consecutive matrices ek boundary dimension share karti hain ($p_1$, $p_2$, $p_3$), aur exactly isi wajah se unhe multiply kiya ja sakta hai — inner dimensions automatically match ho jaate hain. Matrices ki sankhya $=$ $p$ ki length minus one $=5-1=4$.

Cost $=a\cdot b\cdot c=5\cdot 4\cdot 6=120$. Kyon: result $5\times 6=30$ entries ka hoga, aur har entry length $4$ ka dot product hai (wo shared middle dimension), toh $30\times 4=120$.

Sirf do matrices hain, toh sirf ek split hai ($k=1$): $m[1][2]=m[1][1]+m[2][2]+p_0{p}_1{p}_2=0+0+10\cdot 20\cdot 30=6000.$ Min kyon nahi chahiye: do matrices ke saath parentheses rakhne ki exactly ek hi jagah hoti hai.

Chain $A_1{A}_2{A}_3$, indices $i=1,j=3$. Pehle sub-costs:

• $m[1][2]=p_0{p}_1{p}_2=10\cdot 100\cdot 5=5000$
• $m[2][3]=p_1{p}_2{p}_3=100\cdot 5\cdot 50=25000$

Ab do outer splits:

• $k=1$: $m[1][1]+m[2][3]+p_0{p}_1{p}_3=0+25000+10\cdot 100\cdot 50=25000+50000=75000$
• $k=2$: $m[1][2]+m[3][3]+p_0{p}_2{p}_3=5000+0+10\cdot 5\cdot 50=5000+2500=7500$

$m[1][3]=\min (75000,7500)=7500$ at $k=2$ → parenthesization $(A_1{A}_2)A_3$.

$k=2$ kyon jeetta hai: $A_2$ ke baad split karne se final combine $10\cdot 5\cdot 50$ bahut chhoti ho jaati hai, kyunki badi dimension $100$ pehle hi saste $m[1][2]$ step ke andar "kha" li gayi hai.

Matrices: $A_1(40\times 20),A_2(20\times 30),A_3(30\times 10),A_4(10\times 30)$, $n=4$.

Length 2:

• $m[1][2]=40\cdot 20\cdot 30=24000$
• $m[2][3]=20\cdot 30\cdot 10=6000$
• $m[3][4]=30\cdot 10\cdot 30=9000$

Length 3:

• $m[1][3]$:
  • $k=1$: $0+6000+40\cdot 20\cdot 10=6000+8000=14000$
  • $k=2$: $24000+0+40\cdot 30\cdot 10=24000+12000=36000$
  • min $=14000$, $s[1][3]=1$
• $m[2][4]$:
  • $k=2$: $0+9000+20\cdot 30\cdot 30=9000+18000=27000$
  • $k=3$: $6000+0+20\cdot 10\cdot 30=6000+6000=12000$
  • min $=12000$, $s[2][4]=3$

Length 4:

• $k=1$: $m[1][1]+m[2][4]+p_0{p}_1{p}_4=0+12000+40\cdot 20\cdot 30=12000+24000=36000$
• $k=2$: $m[1][2]+m[3][4]+p_0{p}_2{p}_4=24000+9000+40\cdot 30\cdot 30=33000+36000=69000$
• $k=3$: $m[1][3]+m[4][4]+p_0{p}_3{p}_4=14000+0+40\cdot 10\cdot 30=14000+12000=26000$

$m[1][4]=\min (36000,69000,26000)=26000$ at $k=3$, $s[1][4]=3$.

Reconstruct: $s[1][4]=3\Rightarrow (A_1{A}_2{A}_3)(A_4)$. Phir $s[1][3]=1\Rightarrow (A_1(A_2{A}_3))$. Final: $((A_1(A_2{A}_3))A_4)$.

Neeche table-filling order dekho — chains diagonal ke saath badhti hain, kabhi row by row nahi.

$m[1][4]$ ke liye splits $k\in \{1,2,3\}$ ko ye pairs chahiye:

• $k=1$: $m[1][1]$ aur $m[2][4]$
• $k=2$: $m[1][2]$ aur $m[3][4]$
• $k=3$: $m[1][3]$ aur $m[4][4]$

Toh ise $\{m[1][1],m[1][2],m[1][3],m[2][4],m[3][4],m[4][4]\}$ chahiye — ye sab chhote chains hain (length $\le 3$). Isi wajah se hum increasing length $L$ se fill karte hain: length $L$ ki har cell sirf length $<L$ wali cells mein jaati hai, jo pehle se bhar chuki hoti hain. Neeche figure mein arrows dekho.

$n$ matrices ke parenthesizations ki sankhya Catalan number $C_{n-1}$ hai: $C_m=\frac{1}{m+1}\left(\genfrac{}{}{0ex}{}{2m}{m}\right).$ $n=5$ ke liye humein $C_4$ chahiye: $C_4=\frac{1}{5}\left(\genfrac{}{}{0ex}{}{8}{4}\right)=\frac{1}{5}\cdot 70=14.$ Catalan kyon: outermost split point $k$ choose karna recursively ek left group aur ek right group banata hai, aur $C_{n-1}=\sum C_{\text{left}}\cdot C_{\text{right}}$ — exactly Catalan recurrence. Dekho Catalan Numbers. Ye exponential growth ($\sim 4^n/n^{1.5}$) exactly isi wajah se brute force hopeless hai aur DP ($O(n^3)$) jeetta hai.

memo = 2D array filled with -1
def solve(i, j):
    if i == j: return 0
    if memo[i][j] != -1: return memo[i][j]
    best = +infinity
    for k in i..j-1:
        cost = solve(i,k) + solve(k+1,j) + p[i-1]*p[k]*p[j]
        best = min(best, cost)
    memo[i][j] = best
    return best
# answer = solve(1, n)

Same complexity kyon: $O(n^2)$ distinct $(i,j)$ states hain (memo ki wajah se har ek sirf ek baar solve hota hai), aur har ek $k$ par $O(n)$ loop karta hai → $O(n^3)$ time. Space $O(n^2)$ memo table hai (plus $O(n)$ recursion stack). Ye Memoization vs Tabulation equivalence hai: same states, same transitions, alag visiting order. Dekho Time Complexity Analysis.

Dono interval DP hain: ek sub-range ko ek special element fix karke aur do pieces par recurse karke solve karo. MCM mein tum last multiplication fix karte ho ($k$ par split), aur dono sides independent hain kyunki ek completed block sirf apni outer dimensions expose karta hai. Burst Balloons mein tum last balloon burst fix karte ho (pehla nahi!) — kyunki jab $k$ $(i,j)$ ke andar last pop hota hai, uske neighbours exactly survivors $i$ aur $j$ hote hain, jisse do sub-intervals independent ho jaate hain. Ek conceptual switch: LAST event fix karo, pehla nahi, taaki subproblems decouple ho jaayein. Combine term $p_{i-1}{p}_k{p}_j$ (MCM) $v_i{v}_k{v}_j$ (balloons) ban jaata hai — same "teen boundary values multiplied" shape. Ye same "har split/root try karo" pattern Optimal Binary Search Tree ko bhi drive karta hai.

"Sum then min" ko "har split ke liye teen pieces ka max lo, phir $k$ par min karo" se replace karo: $M[i][j]={\min }_{i\le k<j}\max (M[i][k],M[k+1][j],p_{i-1}{p}_k{p}_j),M[i][i]=0.$ Max andar kyon: peak sabse buri single operation hai is raaste mein, toh pieces combine karne par $\{$left ka peak, right ka peak, ye combine$\}$ mein se sabse bada lena padta hai. Min bahar kyon: hum abhi bhi split choose kar sakte hain, toh hum woh chunte hain jiska peak sabse chhota ho.

$p=[10,100,5,50]$ ke liye compute karo ($A_1(10\times 100),A_2(100\times 5),A_3(5\times 50)$):

• $M[1][2]=p_0{p}_1{p}_2=10\cdot 100\cdot 5=5000$
• $M[2][3]=p_1{p}_2{p}_3=100\cdot 5\cdot 50=25000$
• $M[1][3]$:
  • $k=1$: $\max (M[1][1],M[2][3],p_0{p}_1{p}_3)=\max (0,25000,50000)=50000$
  • $k=2$: $\max (M[1][2],M[3][3],p_0{p}_2{p}_3)=\max (5000,0,2500)=5000$
  • min $=5000$ at $k=2$.

Toh minimum peak $5000$ hai $(A_1{A}_2)A_3$ ke saath. Insight: recurrence ka skeleton (interval DP, $k$ par split) untouched hai — sirf aggregation operators bade hain (sum→max). Ye pehchanna ki "paradigm split hai, objective swappable hai" — yahi L5 mastery point hai.

Increasing chain length se fill karo? ::: Haan — $L=2\dots n$, kabhi row by row nahi. Split $k$ par $A_i\cdots A_j$ ke liye combine cost? ::: $p_{i-1}{p}_k{p}_j$. $n$ matrices ke parenthesizations ki sankhya? ::: Catalan $C_{n-1}$. MCM ko "peak cost minimize karo" mein kaise switch karein? ::: Inner sum ko max se replace karo, outer min rakho. Interval-DP golden rule? ::: LAST event fix karo taaki subproblems decouple hon.