Foundations — DP problems — matrix chain multiplication

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

Is page par assume kiya gaya hai ki tumne kuch bhi nahi dekha. parent MCM note padhne se pehle, jo bhi symbol woh tumhare saamne phenkta hai, pehle unhe earn karna hoga. Hum unhe ek-ek karke build karte hain, har ek pichle ke upar.

0. Matrix asal mein hoti kya hai?

Figure dekho. Magenta grid mein $2$ rows aur $3$ columns hain, isliye yeh ek $2\times 3$ matrix hai. Bahar ke chhote labels dimensions hain. Bas itna hi vocabulary chahiye — is page par hum grid ke andar kabhi nahi dekhte, sirf uski shape dekhte hain.

Shape kyun, contents kyun nahi? Kyunki MCM poochhta hai "multiplication mein kitna kaam lagega?", aur — jaise hum dekhenge — workload sirf shape par depend karta hai, andar ke actual numbers par kabhi nahi.

1. Do matrices ko multiply karna — shape ka rule

Koi bhi do matrices ko directly multiply nahi kar sakte. Unki shapes ke baare mein ek rule hai.

Picture mein inner numbers (violet, beech mein touch karte hue) match hone chahiye — yeh shared dimension $b$ hai. Outer numbers (orange) bach jaate hain aur answer ki shape ban jaate hain. Yaad rakhne ka ek aasaan tarika:

$\underset{\text{first}}{\underbrace{a\times b}}\cdot \underset{\text{second}}{\underbrace{b\times c}}=\underset{\text{answer}}{\underbrace{a\times c}}$

2. EK multiplication ki cost — $a\cdot b\cdot c$ kahan se aata hai

Ab iska core: ek matrix multiply mein kitna kaam hota hai? Hum §1 ke wahi $a,b,c$ rakhte hain — left par $a$ rows, shared middle $b$, right par $c$ columns.

Figure mein ek highlighted output cell (orange) dikhai gayi hai. Ise compute karne ke liye, hum length $b$ ki shared strip (violet) ke saath slide karte hain, $b$ multiplications karte hue. Aise $a\cdot c$ cells hain, isliye hum $b$ utni baar pay karte hain.

Multiplications count kyun karo, additions kyun nahi? Lambi tradition ki wajah se, aur isliye ki real hardware par multiplications historically cost mein dominant rehti theen. Parent note is convention ko fix karta hai; hum isse follow karte hain.

3. Ek dimension array $p$ poori chain kyun describe karta hai

Parent note kabhi matrices ki shapes alag-alag list nahi karta. Uski jagah woh ek single array $p$ use karta hai. Yeh kyun kaafi hai.

Figure dekho: har $A_i$ do adjacent $p$-values ke beech straddle karta hai. $A_1$ $[p_0,p_1]$ par baitha hai, $A_2$ $[p_1,p_2]$ par, aur woh $p_1$ share karte hain — jo exactly matching-inner-dimensions rule hai, automatically satisfy hota hua.

4. Subscript aur index $i$

$A$ ya $p$ ke neeche ka chhota number ek subscript hai — ek nametag, arithmetic nahi. $A_i$ matlab "i-th matrix"; $p_{i-1}$ matlab "position $i$ ke left mein ek step $p$-value".

Recurrence mein hum teeno ek saath dekhenge: $i$ (ek sub-chain ka start), $j$ (ek sub-chain ka end), aur $k$ (woh jagah jahan hum cut karte hain). Inhe alag rakhna: $i$ aur $j$ ends hain; $k$ unke beech ghooma karta hai.

5. Parenthesization — brackets ke saath pairing karna

Figure ke dono trees same final matrix produce karte hain — yeh ek property hai jise associativity kehte hain (product mein brackets ko rearrange karne se answer nahi badalta). Lekin, jaise §2 ne dikhaya, do orders mein kaafi alag costs aa sakti hain. Yahi gap MCM ke hone ka poora reason hai, aur yeh Catalan Numbers se connect hota hai, jo batata hai kitne bracketings possible hain.

6. Do words jo DP ko kaam karvaate hain

Parent note do phrases par lean karta hai. Yahan har ek ka matlab picture ke roop mein hai.

7. DP table, uska base case, aur yeh kaise fill hota hai

Ab hum storage ko naam de sakte hain aur — finally — formula assemble kar sakte hain.

Figure dikhata hai kyun loop length ke order mein hai: ek length-3 entry fill karne ke liye (upar), arrows dikhate hain yeh length-2 aur length-1 entries mein neeche jaata hai — jo sirf tabhi exist karte hain agar hum unhe pehle se fill kar chuke hain. Row-by-row fill karo aur tum aisi numbers maangoge jo abhi hain hi nahi. Length ke hisaab se fill karo, sabse chhhoti pehle, aur tumhari zaroori har value guaranteed ready hogi.

8. Recurrence assemble karna — ab sare symbols earn ho chuke hain

Har piece define hai: $A_i$ ($=p_{i-1}\times p_i$), cut index $k$, ek combine ki cost $p_{i-1}{p}_k{p}_j$, table $m$, sare cuts par $\min$, base case. Yahan yeh sab kaise fit hote hain.

Upar define kiya hua har cheez is formula mein exactly ek slot mein fit hoti hai. Yahi payoff hai: yahan ek bhi symbol naya nahi hai.

Prerequisite map (pieces formula mein kaise feed hote hain)

Is map ko ek flow ki tarah padho: shape rule aur cost formula (upar) dono cost of a bracketing mein feed hote hain; base case aur length-ordering table mein feed hoti hai; aur sab kuch neeche ek MCM recurrence par converge hota hai. Koi bhi arrow trace karo aur tumhe bol paana chahiye kyun woh dependency exist karti hai.

Equipment checklist

Term padho, zor se jawab do, phir reveal karo.

Connections

• Parent topic — full MCM note
• Dynamic Programming — woh paradigm jisme yeh foundations feed hoti hain
• Catalan Numbers — kitne parenthesizations exist karte hain
• Memoization vs Tabulation — overlapping subproblems exploit karne ke do tarike
• Optimal Binary Search Tree · Burst Balloons — same interval-DP shape
• Time Complexity Analysis — kyun brute force hopeless hai