DP problems — matrix chain multiplication — Hinglish notes

3.7.13 · Coding › Algorithm Paradigms

YEH problem HAI KYA?

Dimension array KYO? Kyunki matrices ke contents se koi fark nahi padta — sirf cost matter karti hai, aur cost sirf dimensions par depend karti hai.

PARENTHESIZATION matter KYO karti hai? (worked motivation)

Lo $A_{1} (10 \times 100), A_{2} (100 \times 5), A_{3} (5 \times 50)$ , yani $p = [10, 100, 5, 50]$ .

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

Recurrence KAISE derive karein (scratch se)

Key insight: $A_{i} \dots A_{j}$ ki kisi bhi full parenthesization mein ek aakhri multiplication hoti hai. Woh aakhri multiply chain ko kisi point $k$ par split karti hai: $(A_{i} \dots A_{k}) (A_{k + 1} \dots A_{j})$

Left block ek $p_{i - 1} \times p_{k}$ matrix produce karta hai.
Right block ek $p_{k} \times p_{j}$ matrix produce karta hai.
Unhe combine karne ki cost $p_{i - 1} p_{k} p_{j}$ hai.

Yeh decomposition KYO kaam karta hai: har parenthesization mein exactly ek outermost split hota hai. Agar hum best split $k$ jaante, toh subproblems "left ka best cost" aur "right ka best cost" independent hain — yahi optimal substructure hai.

Maano $m [i] [j]$ = $A_{i} \dots A_{j}$ multiply karne ki minimum cost.

Figure — DP problems — matrix chain multiplication

Bottom-up algorithm

MCM(p[0..n]):
    n = len(p) - 1                 # number of matrices
    m = 2D array, m[i][i] = 0
    s = 2D array                   # to reconstruct the splits
    for L in 2..n:                 # chain length
        for i in 1..n-L+1:
            j = i + L - 1
            m[i][j] = +infinity
            for k in i..j-1:
                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
    return m[1][n], s

Pura worked example

Matrices ke saath $p = [30, 35, 15, 5, 10]$ → $A_{1} (30 \times 35), A_{2} (35 \times 15), A_{3} (15 \times 5), A_{4} (5 \times 10)$ , toh $n = 4$ .

Length 2 chains (pairs ki cost):

$m [1] [2] = p_{0} p_{1} p_{2} = 30 \cdot 35 \cdot 15 = 15750$ — Kyun? sirf ek split $k = 1$ hai.
$m [2] [3] = 35 \cdot 15 \cdot 5 = 2625$
$m [3] [4] = 15 \cdot 5 \cdot 10 = 750$

Length 3 chains:

$m [1] [3] = min {k = 1 : m [1] [1] + m [2] [3] + p_{0} p_{1} p_{3} = 0 + 2625 + 30 \cdot 35 \cdot 5 = 2625 + 5250 = 7875 k = 2 : m [1] [2] + m [3] [3] + p_{0} p_{2} p_{3} = 15750 + 0 + 30 \cdot 15 \cdot 5 = 15750 + 2250 = 18000 = 7875 (k = 1)$

Yeh step kyun? Hum $A_{1}$ ke baad split karne ko $A_{2}$ ke baad split karne se compare kar rahe hain; sasta wala $k = 1$ par split hai.
$m [2] [4] = min {k = 2 : 0 + 750 + 35 \cdot 15 \cdot 10 = 750 + 5250 = 6000 k = 3 : 2625 + 0 + 35 \cdot 5 \cdot 10 = 2625 + 1750 = 4375 = 4375 (k = 3)$

Length 4 chain (answer): $m [1] [4] = min ⎩ ⎨ ⎧ k = 1 : m [1] [1] + m [2] [4] + p_{0} p_{1} p_{4} = 0 + 4375 + 30 \cdot 35 \cdot 10 = 4375 + 10500 = 14875 k = 2 : m [1] [2] + m [3] [4] + p_{0} p_{2} p_{4} = 15750 + 750 + 30 \cdot 15 \cdot 10 = 16500 + 4500 = 21000 k = 3 : m [1] [3] + m [4] [4] + p_{0} p_{3} p_{4} = 7875 + 0 + 30 \cdot 5 \cdot 10 = 7875 + 1500 = 9375$ $= 9375 (k = 3)$

Common mistake Common errors ko steel-man karna

Mistake 1: "Greedy — hamesha wahan split karo jahan dimension sabse chota ho." Kyun sahi lagta hai: choti dimensions sasti lagti hain. Kyun galat hai: locally sasta split baad mein expensive combine force kar sakta hai. 7500 vs 75000 wala example dikhata hai greedy fail hoti hai. Fix: saare splits try karna zaroori hai (DP).

Mistake 2: Dimension array mein off-by-one. Kyun sahi lagta hai: log $A_{i}$ ko $p_{i} \times p_{i + 1}$ index karte hain. Kyun galat/confusing hai: standard convention hai $A_{i} = p_{i - 1} \times p_{i}$ , aur split cost $p_{i - 1} p_{k} p_{j}$ hai (naki $p_{i} p_{k} p_{j}$ ). Fix: yaad karo " $A_{i}$ mein $p_{i - 1}$ aur $p_{i}$ use hote hain".

Mistake 3: Table ko row-by-row fill karna. Kyun sahi lagta hai: hum tables aise hi padhte hain. Kyun galat hai: $m [i] [j]$ ko choti chains chahiye jo abhi compute nahi hui hoti. Fix: chain length $L$ ke hisaab se loop karo, $i$ ke hisaab se nahi.

Mistake 4: Multiplications ki jagah additions count karna. Cost = scalar multiplications $= ab c$ ; additions ignore karte hain.

Recall Feynman: 12-saal ke bachche ko samjhao

Socho tumhe LEGO sheets ki ek row ko do-do karke jodhna hai. Do sheets jodhne mein mehnat lagti hai jo unke size par depend karti hai. Final badi sheet same rahegi chahe kisi bhi order mein jodo, lekin kuch orders mein kaam bahut kam lagta hai. MCM bas ek smart plan hai: har woh jagah try karo jahan aakhri glue laga sakte ho, har piece banane ka sabse sasta tarika yaad rakho, aur koi bhi piece dobara solve mat karo.

Flashcards

MCM convention mein matrix

A_{i}

ki dimension kya hoti hai?

p_{i - 1} \times p_{i}

, dimension array

p [0.. n]

use karke.

a \times b

b \times c

matrix se multiply karne ki cost kya hai?

a \cdot b \cdot c

scalar multiplications.

MCM recurrence batao.

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

Saare split points

k

kyun try karte hain?

Hum nahi jaante optimal last multiplication kahan hai; greedy fail hoti hai, isliye sab try karo aur min lo (optimal substructure + overlapping subproblems).

DP table kis order mein fill karte hain?

Increasing chain length

L = j - i + 1

ke hisaab se (length 2 se

n

tak), row by row nahi.

MCM DP ki time aur space complexity?

Time

O (n^{3})

(L, i, k ke loops), space

O (n^{2})

A_{1} (10 \times 100), A_{2} (100 \times 5), A_{3} (5 \times 50)

ki cost

(A_{1} A_{2}) A_{3}

A_{1} (A_{2} A_{3})

mein kya hai?

7500 vs 75000 — same result, 10 guna fark.

Actual parenthesization kaise recover karte hain?

Split point

s [i] [j] = k

store karo, phir

[i, k]

aur

[k + 1, j]

par recurse karo.

Parenthesization result matrix kyun nahi badalta?

Matrix multiplication associative hoti hai.

Base case kya hai aur kyun?

m [i] [i] = 0

kyunki ek akeli matrix ko multiply karne ki zarurat nahi hoti.

Connections

Dynamic Programming — optimal substructure + overlapping subproblems
Catalan Numbers — parenthesizations count karta hai $C_{n - 1}$
Optimal Binary Search Tree — same "har root/split try karo" interval-DP pattern
Burst Balloons — interval DP jahan last element fix karte hain
Memoization vs Tabulation
Time Complexity Analysis — $O (n^{3})$ teen nested loops se