DP problems — matrix chain multiplication: Visual walkthrough

3.7.13 · D2 · Coding › Algorithm Paradigms › DP problems — matrix chain multiplication

Hum poore walkthrough mein ek hi chain use karenge: $A_{1} (30 \times 35), A_{2} (35 \times 15), A_{3} (15 \times 5), A_{4} (5 \times 10)$ toh dimension array (wo list of numbers jo saari shapes describe karta hai) hai $p = [p_{0}, p_{1}, p_{2}, p_{3}, p_{4}] = [30, 35, 15, 5, 10] .$

Step 1 — Matrix ki "shape" kya hoti hai, aur ek multiplication kitni cost karti hai

KYA. Matrix sirf numbers ka ek grid hota hai. Uski shape rows × columns likhi jaati hai. Matrix $A_{2}$ hai $35 \times 15$ : 35 rows, 15 columns. Dimension array mein, $A_{i}$ ki shape hai $p_{i - 1} \times p_{i}$ — wo rows ke liye left wala number ( $p_{i - 1}$ ) lete hai aur columns ke liye right wala number ( $p_{i}$ ).

WHY sirf shapes. Effort count karne ke liye hume andar ke actual numbers ki zarurat nahi — effort sirf is baat par depend karta hai ki grids kitne bade hain. Toh hum contents hata dete hain aur sirf shape list $p$ rakhte hain.

PICTURE. Ek $a \times b$ grid ko $b \times c$ grid se multiply karne ke liye, do inner numbers match karne chahiye (dono $b$ ). Tum ek $a \times c$ result produce karte ho, aur uske $a \cdot c$ cells mein se har cell $b$ products ka sum hota hai.

Figure — DP problems — matrix chain multiplication

Step 2 — Do orders, bilkul alag bills

KYA. Sirf pehli teen matrices lo aur unhe do-do karke jodo. Do possible orders exist karte hain. Final grid identical hoti hai (matrix multiplication associative hoti hai), lekin scalar multiplications ka running total nahi hota.

WHY ye matter karta hai. Agar dono orders ki cost same hoti toh koi problem hi nahi hoti solve karne ki. Hoti nahi hai — kabhi kabhi 10 ya usse zyada ka factor — toh order choose karna real kaam hai.

PICTURE. Dekho ki har order kaunsa intermediate grid build karta hai. Mota intermediate grid hi ek order ko expensive banata hai.

$p = [10, 100, 5, 50]$ use karte hain (zyada sharp illustration ke liye):

$(A_{1} A_{2}) A_{3} : 5000 10 \cdot 100 \cdot 5 + 2500 10 \cdot 5 \cdot 50 = 7500$ $A_{1} (A_{2} A_{3}) : 25000 100 \cdot 5 \cdot 50 + 50000 10 \cdot 100 \cdot 50 = 75000$

Step 3 — Ek hi idea: LAST glue dekho

KYA. Bhool jao ki poora product kaise build hota hai. Sirf poocho: kaunsi multiplication sabse last hoti hai? Chahe kuch bhi parenthesization ho, exactly ek outermost multiply hoti hai, aur wo ek left block ko ek right block se jodti hai.

WHY ye question. Ye ek mushkil problem ko do chhote, independent problems mein tod deta hai. Agar last glue matrix $A_{k}$ ke baad hai, toh:

left side ki sab cheez, $A_{i} \dots A_{k}$ , ek grid mein collapse ho chuki hai,
right side ki sab cheez, $A_{k + 1} \dots A_{j}$ , ek grid mein collapse ho chuki hai,
aur unki internal costs ek doosre ko affect nahi karti. Yahi optimal substructure hai.

PICTURE. Split point $k$ chain mein ek single cut hai. Dono halves apne aap mein chhote MCM problems hain.

Step 4 — Last glue ki cost kya hoti hai

KYA. Dono halves collapse hone ke baad, hum unki shapes $p$ se exactly jaante hain:

Left block $A_{i} \dots A_{k}$ ek $p_{i - 1} \times p_{k}$ grid produce karta hai.
Right block $A_{k + 1} \dots A_{j}$ ek $p_{k} \times p_{j}$ grid produce karta hai.

WHY ye shapes. Left block $A_{i}$ se start hota hai (rows $p_{i - 1}$ ) aur $A_{k}$ par khatam hota hai (columns $p_{k}$ ). Right block $A_{k + 1}$ se start hota hai (rows $p_{k}$ ) aur $A_{j}$ par khatam hota hai (columns $p_{j}$ ). Do inner numbers dono $p_{k}$ hain — ye automatically match karte hain, isliye consecutive blocks ko hamesha glue kiya ja sakta hai.

PICTURE. Teen boundary numbers bachte hain: $p_{i - 1}$ , $p_{k}$ , $p_{j}$ . Step 1 ke rule se final glue ki cost unka product hai.

Step 5 — Recurrence assemble karna

KYA. Jo cheez chahiye usse naam do: $m [i] [j]$ ko minimum number of scalar multiplications maano jo $A_{i} \dots A_{j}$ ko fully collapse karne ke liye chahiye. Chosen split $k$ ke liye total cost hai: left half ki cost + right half ki cost + final glue.

WHY $k$ par min. Hume advance mein best cut nahi pata (Step 2 ne prove kiya ki greedy guessing fail hoti hai). Toh hum har legal cut $k$ try karte hain aur sabse sasta rakhte hain — yahi ek honest choice hai.

PICTURE. Har candidate $k$ ek branch hai. Hum sab evaluate karte hain aur sabse chhota bar chunte hain.

Step 6 — Degenerate aur edge cases (koi gap mat chhodo)

KYA. Har wo corner jo reader encounter kar sakta hai:

Ek matrix ( $i = j$ ): min ke liye koi valid $k$ nahi hai (range $i \leq k < j$ empty hai). Hume empty set par min nahi call karna chahiye → yahi reason hai ki base case $m [i] [i] = 0$ ek alag branch ki tarah exist karta hai.
Do matrices ( $j = i + 1$ ): exactly ek legal $k = i$ . Koi real choice nahi, cost sirf $p_{i - 1} p_{i} p_{i + 1}$ hai — Step 1 ke single-multiply cost se match karta hai, jaise hona chahiye.
Ek dimension equal to 1 (jaise row ya column vector): formula phir bhi kaam karta hai; product mein $1$ sirf us glue ko cheap bana deta hai. Kuch special-case nahi.
Empty chain ( $n = 0$ , array length 1): koi matrices nahi, cost $0$ — loops se pehle guard karo.

WHY ye dikhate hain. Ek recurrence jo smallest input par crash kare wo complete nahi hai. Base case decoration nahi hai; ye woh floor hai jis par poori recursion khadi hai.

PICTURE. Recursion tree tab tak bottom out hota hai jab tak har leaf ek single matrix (cost 0) na ho.

Step 7 — Chain LENGTH se fill kyun karo, rows se nahi

KYA. $m [i] [j]$ compute karne ke liye hume $m [i] [k]$ aur $m [k + 1] [j]$ chahiye — dono chhoti chains hain. Toh kisi bhi lambi chain se pehle hume saari chhoti chains milni chahiye.

WHY row-by-row nahi. Table ko left-to-right, top-to-bottom padhne par $m [1] [4]$ (length 4) maangega jabki $m [2] [4]$ (length 3) abhi blank hoga. Badh ke length $L = j - i + 1$ se fill karo: $L = 1$ (zeros), phir $L = 2$ , $L = n$ tak.

PICTURE. DP table main diagonal se bahar sweep karte diagonals ki tarah fill hoti hai.

Apni chain $p = [30, 35, 15, 5, 10]$ par kaam karte hain:

$m [1] [2] = 15750, m [2] [3] = 2625, m [3] [4] = 750 (L = 2)$ $m [1] [3] = 7875 (k = 1), m [2] [4] = 4375 (k = 3) (L = 3)$ $m [1] [4] = min {14875, 21000, 9375} = 9375 (k = 3) (L = 4)$

Recall 9375 kahan se aaya?

Poori chain ka best split $k = 3$ hai ::: $((A_{1} A_{2} A_{3}) A_{4})$ , aur andar $s [1] [3] = 1$ deta hai $(A_{1} (A_{2} A_{3}))$ , toh answer hai $((A_{1} (A_{2} A_{3})) A_{4})$ cost 9375 par.

Ek-picture summary

Upar ki saari cheez ek single frame mein compress ki: chain, $k$ par ek last cut, do collapsed halves, teen surviving boundary numbers glue cost ko feed karte hain, aur saare cuts par min DP table ko length se fill karta hai.

Recall Feynman retelling — poora walkthrough simple words mein

Tumhare paas paper sheets ki ek row hai jise stack-glue karna hai, do at a time. Ek $a \times b$ sheet ko $b \times c$ sheet se glue karne ki cost $a \cdot b \cdot c$ effort hai (Step 1). Final sheet gluing order chahe kuch bhi ho same dikhti hai, lekin effort 10× differ kar sakta hai kyunki mote middle sheets expensive hote hain (Step 2). Trick: sabse last glue ke baare mein socho — wo hamesha row ko ek left piece aur ek right piece mein split karta hai jo independently build hue the (Step 3). Ek baar split hone par, dono pieces ki shapes boundary numbers se fix ho jaati hain, toh last glue ki cost $p_{i - 1} p_{k} p_{j}$ hoti hai (Step 4). Hume best jagah cut karna nahi pata, toh hum har cut try karte hain aur sabse sasta rakhte hain — yahi $k$ par min hai (Step 5). Ek sheet ki cost kuch nahi, jo puri idea ka floor hai (Step 6). Aur kyunki lambi piece chhoti pieces se banti hai, hum pehle chhoti pieces solve karte hain, table ko length se sweep karte hain (Step 7). Yahi poora algorithm hai — ek honest "try all last cuts" cleverly repeat kiya.

Connections

Dynamic Programming — Step 5 ke peeche optimal-substructure engine
Catalan Numbers — kitne parenthesizations exist karte hain ( $C_{n - 1}$ ), yani brute force kyun haarta hai
Optimal Binary Search Tree — same "try every split" interval-DP shape
Burst Balloons — interval DP jahan tum last balloon fix karte ho
Memoization vs Tabulation — top-down vs yahan ka length-sweep
Time Complexity Analysis — $O (n^{3})$ loops over $L, i, k$ se