DP problems — matrix chain multiplication: Worked examples

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

Shuru karne se pehle, woh objects yaad karo jo hum baar baar use karte hain — jisme se ek, split table, itna zyada kaam aata hai ki uski apni definition deserve karti hai.

Definition Woh tools jinpe hum depend karte hain (split table ko explicitly define karke)

Dimension array $p = [p_{0}, p_{1}, \dots, p_{n}]$ . Matrix $A_{i}$ hai $== p_{i - 1} \times p_{i} ==$ . Toh $n$ matrices ko $n + 1$ numbers chahiye. Length $1$ ka array (sirf $[p_{0}]$ ) matlab $n = 0$ — zero matrices.
Combine cost ek $a \times b$ block ko $b \times c$ block se glue karne ka hai $== a \cdot b \cdot c ==$ scalar multiplications — har output entry ( $a \cdot c$ ki count) ke liye ek multiply times shared length $b$ .
Cost table $m [i] [j]$ = $A_{i} \dots A_{j}$ banane ke liye minimum multiplications. Recurrence: $m [i] [j] = min_{i \leq k < j} (m [i] [k] + m [k + 1] [j] + p_{i - 1} p_{k} p_{j})$ , with $m [i] [i] = 0$ .
Split table $s [i] [j]$ = interval $[i, j]$ ke liye winning cut point $k$ . Jab bhi upar wala min kisi $k$ par achieve ho, hum $s [i] [j] = k$ record karte hain. Yeh doosra table cost ke baare mein kuch store nahi karta — sirf yeh ki sabse sasta last multiplication kahan hua — taaki baad mein hum actual brackets rebuild kar sakein. Cost batata hai kitna; split table batata hai kaise.

Kyunki neeche ke do examples in tables ko code-order mein fill karte hain, yahan exact loop structure hai jo hum follow karte hain — variable names ( $L$ , $i$ , $j$ , $k$ ) baad mein verbatim use hote hain, isliye inhe abhi se jaano:

n = len(p) - 1                     # number of matrices
m[i][i] = 0 for all i              # base case
for L in 2..n:                     # L = chain length, OUTERMOST
    for i in 1..n-L+1:             # left end of the interval
        j = i + L - 1              # right end (so length is exactly L)
        m[i][j] = +infinity
        for k in i..j-1:           # try every last-cut position
            cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if cost < m[i][j]:
                m[i][j] = cost
                s[i][j] = k        # <-- remember the winning split

The scenario matrix

Har MCM input in case classes mein se ek mein aata hai. Last column us worked example ka naam batata hai jo use cover karta hai, taaki tum dekh sako ki poora space filled hai — genuinely empty chain se shuru karke.

Case class	Kya special hai	Covered by
Empty chain: $n = 0$	array length $1$ , bilkul bhi matrices nahi	Example 0
Degenerate: $n = 1$	ek matrix, kuch multiply nahi hota	Example 1
Minimal branch: $n = 2$	exactly ek split, koi choice nahi	Example 2
First real choice: $n = 3$	do splits compete karte hain	Example 3
All-square chain	har $p_{i}$ equal → symmetry, ties	Example 4
Skinny middle matrix	ek tiny dimension answer badal deta hai	Example 5
Tie between split points	do $k$ equal cost dete hain — kaunsa store karein?	Example 6
Scalar output ( $p_{0} = p_{n} = 1$ )	chain collapse hokar $1 \times 1$ number ban jaata hai	Example 7
Word problem (real world)	ek story ko $p$ array mein translate karo	Example 8
Exam twist: count vs recover	parenthesization maanga hai, sirf cost nahi	Example 9

Hum inhe order mein work karte hain. Har example pehle tumse Forecast karne kehta hai compute karne se pehle — woh guess hi actual learning hai.

Example 0 — Empty chain ( $n = 0$ )

Forecast: agar multiply karne ke liye kuch hai hi nahi, toh kya cost $0$ hai, undefined hai, ya error hai? Padhne se pehle guess karo.

$n$ compute karo. Yeh step kyun? Har MCM run array ko matrix count mein turn karne se shuru hoti hai. Yahan $n = 0$ .
Check karo ki koi loop body execute hoti hai ya nahi. Yeh step kyun? Outer loop for L in 2..n, yaani 2..0, chalata hai — jo empty hai — zero iterations. Koi interval $[i] [j]$ exist nahi karta jahan $i < j$ ho.
Answer padhо. Yeh step kyun? Koi $m [1] [n]$ return karne ke liye nahi hai (koi matrix $A_{1}$ nahi hai). Kuch nahi multiply karne ki total cost convention se $0$ hai, bilkul waise jaise empty sum $0$ hota hai.

$cost = 0$

Verify: Ek empty product ko koi kaam nahi chahiye, toh $0$ hi ek sensible value hai; loops kabhi fire nahi hote, toh kuch break nahi hota. Yeh woh boundary hai jo tumhe code mein handle karni padti hai (if n <= 1: return 0) — units multiplications hain, aur humne koi nahi kiya. ✓

Example 1 — Degenerate: a single matrix ( $n = 1$ )

Forecast: ...agar kuch multiply hi nahi hota toh kitna kaam hai? Padhne se pehle guess karo.

Matrices count karo. Yeh step kyun? Array ki length $2$ hai, aur $n = len (p) - 1 = 1$ . Ek matrix.
Base case apply karo. Yeh step kyun? Recurrence ki pehli branch kehti hai $m [i] [i] = 0$ . Yahan $i = j = 1$ , toh hum seedha base case pe aate hain — koi split point $k$ nahi hai jahan $i \leq k < j$ kyunki $j = i$ .

$m [1] [1] = 0$

Verify: Ek single matrix already "multiplied" hai. Koi scalar multiplication nahi hoti, toh $0$ correct hai — units multiplications hain, aur humne koi nahi kiya. ✓

Example 2 — Minimal branch: exactly one split ( $n = 2$ )

Forecast: sirf do matrices hain toh choose karne ke liye kuch nahi — lekin kaunsa number niklega?

Valid splits list karo. Yeh step kyun? $k$ range karta hai $i \leq k < j$ , yaani $1 \leq k < 2$ , toh sirf $k = 1$ . Minimum lene ki zaroorat nahi — ek candidate, aur toh $s [1] [2] = 1$ automatically.
Combine formula mein plug in karo. Yeh step kyun? Left block $A_{1}$ hai $p_{0} \times p_{1}$ , right block $A_{2}$ hai $p_{1} \times p_{2}$ , toh combine cost hai $p_{0} p_{1} p_{2}$ . Sub-costs $m [1] [1] = m [2] [2] = 0$ .

$m [1] [2] = 0 + 0 + p_{0} p_{1} p_{2} = 10 \cdot 100 \cdot 5 = 5000$

Verify: Output $10 \times 5$ hai, toh $50$ entries, har ek $100$ products ka sum → $50 \times 100 = 5000$ multiplications. Match karta hai. ✓

Example 3 — The first real choice ( $n = 3$ )

Yeh parent note ki motivating chain hai — hum ise sirf do options ke beech decision ke roop mein redo karte hain, $k = 1$ aur $k = 2$ . Exactly do candidate trees hain, aur figure dono draw karta hai taaki tum dekh sako kaunsa survive karta hai.

Forecast: ek split bada $100$ dimension ko ek combine ke andar rakhta hai, doosra use bahar rakhta hai. Kaunsa sasta hai — aur kitna difference hai?

Figure — DP problems — matrix chain multiplication

Figure — do binary trees side by side. Left (teal): $k = 1$ tree $(A_{1}) (A_{2} A_{3})$ ; iska root "×" node leaf $A_{1}$ ko sub-tree $A_{2} A_{3}$ se multiply karta hai, aur uski total cost $75000$ label ki gayi hai. Right (plum): $k = 2$ tree $(A_{1} A_{2}) (A_{3})$ ; yahan $A_{1} A_{2}$ sub-tree hai aur $A_{3}$ lone leaf hai, total cost $7500$ . Burnt-orange arrow label "cheaper split kept by min" se plum tree ke root ki taraf point karta hai — yahi woh branch hai jo $min$ operator rakhta hai, toh $s [1] [3] = 2$ . Har tree ko bottom-up padhо: leaves original matrices hain, har "×" ek multiplication hai, aur tree ki shape HI parenthesization hai.

Splits enumerate karo. Yeh step kyun? $1 \leq k < 3$ deta hai $k = 1$ aur $k = 2$ . Yeh sirf do tarike hain last multiplication place karne ke (figure mein do trees).
Split $k = 1$ : $(A_{1}) (A_{2} A_{3})$ . Yeh step kyun? Left $A_{1}$ hai (cost $0$ ), right $A_{2} A_{3}$ hai (cost $m [2] [3] = 100 \cdot 5 \cdot 50 = 25000$ ), combine $= p_{0} p_{1} p_{3} = 10 \cdot 100 \cdot 50 = 50000$ . $0 + 25000 + 50000 = 75000$
Split $k = 2$ : $(A_{1} A_{2}) (A_{3})$ . Yeh step kyun? Left $A_{1} A_{2}$ hai (cost $m [1] [2] = 10 \cdot 100 \cdot 5 = 5000$ ), right $A_{3}$ (cost $0$ ), combine $= p_{0} p_{2} p_{3} = 10 \cdot 5 \cdot 50 = 2500$ . $5000 + 0 + 2500 = 7500$
Min lo aur split record karo. Yeh step kyun? Recurrence sasta candidate rakhta hai, aur $s [1] [3]$ yaad rakhta hai ki kaunsa $k$ jeeta. $7500 < 75000$ , toh winner hai $k = 2$ .

$m [1] [3] = 7500, s [1] [3] = 2$

Verify: $10 \times$ ka difference, parent note ki headline se match karta hai. Figure mein, plum tree (jise orange arrow mark karta hai) survivor hai — uski shape $(A_{1} A_{2}) A_{3}$ exactly wahi hai jo $s [1] [3] = 2$ encode karta hai. ✓

Example 4 — All-square chain (symmetry & the ties it creates)

Forecast: jab har matrix shape mein identical ho, toh kya split point matter karta hai?

Har combine same cost karta hai. Yeh step kyun? Har factor $p_{i - 1}, p_{k}, p_{j}$ equals $4$ , toh har combine hai $4 \cdot 4 \cdot 4 = 64$ , $k$ se independent.
Har length-2 subchain $64$ cost karta hai. Yeh step kyun? Ek length-2 subchain ka ek hi split hota hai, toh uski cost sirf ek combine $= p_{i - 1} p_{i} p_{i + 1} = 4 \cdot 4 \cdot 4 = 64$ hai; yeh dono $m [1] [2]$ aur $m [2] [3]$ par apply hota hai, deta hai $m [1] [2] = m [2] [3] = 64$ .
Dono splits try karo. Yeh step kyun? Symmetry tie predict karta hai, lekin algorithm phir bhi sabhi $k$ enumerate karta hai ek par trust karne se pehle.
- $k = 1$ : $m [1] [1] + m [2] [3] + 64 = 0 + 64 + 64 = 128$
- $k = 2$ : $m [1] [2] + m [3] [3] + 64 = 64 + 0 + 64 = 128$
Result. Dono $128$ dete hain; min hai $128$ (first-seen $k = 1$ recorded, toh $s [1] [3] = 1$ ).

$m [1] [3] = 128$

Verify: Koi bhi parenthesization exactly do $4 \times 4 \times 4$ multiplies karta hai $= 2 \cdot 64 = 128$ . Equal costs square chain ki hallmark hain — koi order doosre se better nahi. ✓

Example 5 — Skinny middle matrix (ek tiny dimension rules)

Forecast: $10$ (dimension $p_{3}$ ) ek bottleneck hai. Kya acche splits iske through route karne ki koshish karte hain?

Hum chain length $L$ se fill karte hain, exactly waisa jaise upar wala loop skeleton demand karta hai.

Length 2 ( $L = 2$ ):

$m [1] [2] = p_{0} p_{1} p_{2} = 40 \cdot 20 \cdot 30 = 24000$
$m [2] [3] = p_{1} p_{2} p_{3} = 20 \cdot 30 \cdot 10 = 6000$
$m [3] [4] = p_{2} p_{3} p_{4} = 30 \cdot 10 \cdot 30 = 9000$

Length 3 ( $L = 3$ ): Ab kyun? Har ek ko do length- $\leq 2$ answers chahiye, jo humne abhi compute kiye. 4. $m [1] [3] = min {k = 1 : 0 + 6000 + p_{0} p_{1} p_{3} = 6000 + 40 \cdot 20 \cdot 10 = 6000 + 8000 = 14000 k = 2 : 24000 + 0 + p_{0} p_{2} p_{3} = 24000 + 40 \cdot 30 \cdot 10 = 24000 + 12000 = 36000 = 14000 (s [1] [3] = 1)$ 5. $m [2] [4] = min {k = 2 : 0 + 9000 + p_{1} p_{2} p_{4} = 9000 + 20 \cdot 30 \cdot 30 = 9000 + 18000 = 27000 k = 3 : 6000 + 0 + p_{1} p_{3} p_{4} = 6000 + 20 \cdot 10 \cdot 30 = 6000 + 6000 = 12000 = 12000 (s [2] [4] = 3)$

Length 4 ( $L = 4$ , the answer): Last kyun? Yeh sab chhoti chains par depend karta hai. 6. $m [1] [4] = min ⎩ ⎨ ⎧ k = 1 : 0 + 12000 + p_{0} p_{1} p_{4} = 12000 + 40 \cdot 20 \cdot 30 = 12000 + 24000 = 36000 k = 2 : 24000 + 9000 + p_{0} p_{2} p_{4} = 33000 + 40 \cdot 30 \cdot 30 = 33000 + 36000 = 69000 k = 3 : 14000 + 0 + p_{0} p_{3} p_{4} = 14000 + 40 \cdot 10 \cdot 30 = 14000 + 12000 = 26000$

$m [1] [4] = 26000 (s [1] [4] = 3)$

Verify: Winning split $k = 3$ tiny $p_{3} = 10$ ko outer combine mein dalta hai ( $p_{0} p_{3} p_{4} = 40 \cdot 10 \cdot 30$ ), jo sabse sasta boundary hai. "Skinny" dimension ek discount coupon ki tarah kaam karta hai — acche splits use sabse bade combine par kharchte hain. ✓

Example 6 — A deliberate tie between split points

Forecast: shape "upar-neeche-upar" jaati hai. Kya do splits same cost par land karenge?

Length-2 costs. $m [1] [2] = p_{0} p_{1} p_{2} = 2 \cdot 3 \cdot 2 = 12$ ; $m [2] [3] = p_{1} p_{2} p_{3} = 3 \cdot 2 \cdot 3 = 18$ .
Split $k = 1$ : $0 + 18 + p_{0} p_{1} p_{3} = 18 + 2 \cdot 3 \cdot 3 = 18 + 18 = 36$ .
Split $k = 2$ : $12 + 0 + p_{0} p_{2} p_{3} = 12 + 2 \cdot 2 \cdot 3 = 12 + 12 = 24$ .
Min. $24 < 36$ , toh $m [1] [3] = 24$ at $k = 2$ ( $s [1] [3] = 2$ ).

Ab ek true tie — last dimension badlo taaki dono splits same cost karein:

Verify: Tie variant mein, mirror symmetry ( $p$ read hota hai $2, 3, 3, 2$ — ek palindrome) do trees ko same cost karne par majboor karta hai. Algorithm ka answer $30$ optimal hai chahe woh kaunsa bhi $k$ record kare. ✓

Example 7 — Scalar output ( $p_{0} = p_{n} = 1$ )

Forecast: outer dimensions $1$ hain. Kya woh ek split ko almost free banata hai?

Length-2 costs. $m [1] [2] = p_{0} p_{1} p_{2} = 1 \cdot 5 \cdot 4 = 20$ ; $m [2] [3] = p_{1} p_{2} p_{3} = 5 \cdot 4 \cdot 1 = 20$ .
Split $k = 1$ : $(A_{1}) (A_{2} A_{3})$ . $0 + 20 + p_{0} p_{1} p_{3} = 20 + 1 \cdot 5 \cdot 1 = 20 + 5 = 25$ .
Split $k = 2$ : $(A_{1} A_{2}) (A_{3})$ . $20 + 0 + p_{0} p_{2} p_{3} = 20 + 1 \cdot 4 \cdot 1 = 20 + 4 = 24$ .
Min. $24 < 25$ , toh $m [1] [3] = 24$ at $k = 2$ ( $s [1] [3] = 2$ ).

Verify: Kyunki $p_{0} = p_{3} = 1$ , dono outer combines tiny hain ( $5$ aur $4$ ), toh winner decide hota hai inner subchain se. Final matrix genuinely $1 \times 1$ hai — ek plain number — phir bhi intermediate work abhi bhi $24$ multiplications cost karta hai. Degenerate outer shape ≠ free chain. ✓

Example 8 — Word problem (translate the story)

Forecast: kya tumhe teeno tiny $3 \times 3$ -ish transforms pehle fold kar lene chahiye, phir bade $1000$ -row data ko hit karo — ya left to right chalte raho?

$p$ array banao. Yeh step kyun? MCM sirf dimensions dekhta hai. Chain $A_{1} = D (1000 \times 3)$ , $A_{2} = R (3 \times 3)$ , $A_{3} = S (3 \times 3)$ , $A_{4} = P (3 \times 4)$ . Toh $p = [1000, 3, 3, 3, 4] .$
Length-2: $m [1] [2] = 1000 \cdot 3 \cdot 3 = 9000$ ; $m [2] [3] = 3 \cdot 3 \cdot 3 = 27$ ; $m [3] [4] = 3 \cdot 3 \cdot 4 = 36$ .
Length-3:
- $m [1] [3] = min {k = 1 : 0 + 27 + 1000 \cdot 3 \cdot 3 = 27 + 9000 = 9027 k = 2 : 9000 + 0 + 1000 \cdot 3 \cdot 3 = 9000 + 9000 = 18000 = 9027 (s [1] [3] = 1)$
- $m [2] [4] = min {k = 2 : 0 + 36 + 3 \cdot 3 \cdot 4 = 36 + 36 = 72 k = 3 : 27 + 0 + 3 \cdot 3 \cdot 4 = 27 + 36 = 63 = 63 (s [2] [4] = 3)$
Length-4: $m [1] [4] = min ⎩ ⎨ ⎧ k = 1 : 0 + 63 + 1000 \cdot 3 \cdot 4 = 63 + 12000 = 12063 k = 2 : 9000 + 36 + 1000 \cdot 3 \cdot 4 = 9036 + 12000 = 21036 k = 3 : 9027 + 0 + 1000 \cdot 3 \cdot 4 = 9027 + 12000 = 21027$ $= 12063 (s [1] [4] = 1) .$

Result: $s [1] [4] = 1$ matlab last multiply hai $D (R S P)$ : pehle teeno transforms ko fold karo (woh saste $3 \times 3 \times 3$ -ish hain), phir combined $3 \times 4$ matrix ko bade $1000$ -row data par ek baar apply karo.

Verify: Naive left-to-right order cost karta hai $m [1] [3] + 0 + p_{0} p_{3} p_{4} = 9027 + 12000 = 21027$ ( $k = 3$ path); optimal $12063$ kaam ko lagbhag halve kar deta hai — exactly "chhoti cheezein combine karo bade matrix ko touch karne se pehle" wali intuition. ✓

Example 9 — Exam twist: recover the parenthesization, not just the cost

Forecast: tumhe cost pata hai; trick hai split indices ko nested brackets mein turn karna. Pehla bracket kahan close hota hai?

Definition box se yaad karo: $s [i] [j]$ woh cut point $k$ hai jahan interval $[i, j]$ ne apna sabse sasta last multiplication kiya. Brackets rebuild karne ke liye tum $s$ ko top-down padhte ho, sabse bada interval pehle.

Poori chain $[1, 4]$ se shuru karo. Yeh step kyun? Reconstruction hamesha outermost interval se shuru hoti hai. $s [1] [4] = 3$ → $A_{3}$ ke baad last cut: $(A_{1} A_{2} A_{3}) (A_{4})$ .
Left $[1, 3]$ par recurse karo. Yeh step kyun? Uska apna last cut hai $s [1] [3] = 1$ → $(A_{1}) (A_{2} A_{3})$ .
$[2, 3]$ par recurse karo. $s [2] [3] = 2$ → $(A_{2}) (A_{3})$ , yaani sirf $A_{2} A_{3}$ with only possible split.
Right side $[4, 4]$ ek single matrix hai — koi bracket nahi.
Inside-out assemble karo. Yeh step kyun? Pieces substitute karo: $((A_{1} (A_{2} A_{3})) A_{4}) .$

Verify: Yeh parent note ki stated optimal parenthesization se exactly match karta hai, aur uski cost $m [1] [4] = 9375$ hai. $s$ table ko top-down padha jaata hai (sabse bada interval pehle), phir har sub-interval recursively. ✓

Recall Self-test: har ek ke liye case class naam batao

$p = [7]$ (array length $1$ , yaani zero matrices) vs $p = [7, 7, 7, 7]$ vs $p = [1, 9, 9, 1]$ . $p = [7]$ ::: empty chain, $n = 0$ → cost $0$ , koi loop iteration nahi (Example 0). $p = [7, 7, 7, 7]$ ::: all-square chain → har split tie karta hai (Example 4 pattern). $p = [1, 9, 9, 1]$ ::: scalar output, palindrome dims → symmetric tie, final result $1 \times 1$ hai (Examples 6 & 7 combined). Kaunsa loop variable outermost hona chahiye taaki koi subchain unfilled na rahe? ::: chain-length $L$ (grow $L$ from $2$ to $n$ ), kabhi row $i$ se loop mat karo. $s [i] [j]$ kya store karta hai, aur use $m [i] [j]$ se alag kyun rakhte hain? ::: interval $[i, j]$ ke liye winning cut $k$ ; $m$ batata hai kitna, $s$ batata hai kaise, taaki hum brackets rebuild kar sakein.

Connections

3.7.13 DP problems — matrix chain multiplication (Hinglish) — woh parent recurrence jinhe yeh examples exercise karte hain
Dynamic Programming — optimal substructure hi wajah hai ki per-interval answers combine hote hain
Catalan Numbers — in chains mein se har ek ke kitne parenthesizations hain
Optimal Binary Search Tree — same "har split try karo, $s$ store karo" reconstruction
Burst Balloons — interval DP jahan last element (split nahi) fix hota hai
Memoization vs Tabulation — top-down bhi yahi $m [i] [j]$ lazily compute karta
Time Complexity Analysis — upar ke har example ka fill work $O (n^{3})$ hai