DP problems — matrix chain multiplication: Question bank

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

Spot the error

A_{i} \dots A_{j}

k

pe split karne ka combine cost

p_{i} p_{k} p_{j}

hai."

Wrong index. Left block

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

hai aur right

p_{k} \times p_{j}

, isliye cost

p_{i - 1} p_{k} p_{j}

hai — left dimension

p_{i - 1}

hai,

p_{i}

nahi.

a \times b

aur

b \times c

matrix multiply karne ki cost

a + b + c

operations hai."

Galat. Har

a \cdot c

output entry ke liye

b

multiplications lagte hain, isliye total

a \cdot b \cdot c

hota hai. Hum multiplications count karte hain, dimensions ka sum nahi.

"Hum additions aur multiplications dono count karte hain, isliye cost

ab c + a (b - 1) c

hai."

Standard MCM cost sirf scalar multiplications (

ab c

) count karta hai; additions ko convention ke according ignore kiya jaata hai, isliye extra term use nahi hota.

"Greedy: hamesha sabse chhoti dimension

p_{k}

pe split karo, yahi sabse sasta join hai."

Locally sasta combine forced expensive sub-chains bana sakta hai, jisse total worse ho jaata hai. Greedy provably fail karta hai (7500-vs-75000 case), isliye har split try karna padta hai — isliye ye DP hai, greedy nahi.

m [1] [n]

loop for i in 1..n: for j in i..n se milta hai."

Ye states ko wrong dependency order mein visit karta hai. Sahi outer loop chain length

L

ke upar 2 se

n

tak hona chahiye; tabhi saari chhoti sub-chains ready hoti hain.

"Answer reconstruct karne ke liye hum query time pe

k

pe min dobara run karte hain."

Unnecessary aur error-prone hai. Hum fill ke dauran argmin

s [i] [j] = k

mein store karte hain, phir usi table se

[i, k]

aur

[k + 1, j]

pe recurse karte hain.

"Space

O (n^{3})

hai kyunki teen nested loops hain."

Loops time

O (n^{3})

dete hain. Stored tables

m

aur

s

(i, j)

ke upar 2D hain, isliye space

O (n^{2})

hai. Time Complexity Analysis dekho.

Why questions

Hum last multiplication ke baare mein kyun sochte hain, first ke baare mein kyun nahi?

Har full parenthesization mein exactly ek outermost (final) multiply hota hai jo poori chain ko do independent blocks mein split karta hai. Last cut fix karne se problem cleanly separate hoti hai; first multiply baki structure ko same tarah partition nahi karta.

Plain recursion kyun blow up hoti hai jabki DP polynomial hai?

Same sub-chains (jaise

A_{2} A_{3} A_{4}

) bahut saari parenthesizations mein baar baar aate hain — overlapping subproblems. Plain recursion unhe exponentially baar re-solve karta hai; DP har

m [i] [j]

ek baar store karta hai.

Parenthesizations ki count Catalan number ki tarah kyun grow karti hai?

Har parenthesization

n

leaves (matrices) ke ek distinct binary tree ke corresponding hota hai; aisi trees ki count

C_{n - 1}

hoti hai. Catalan Numbers dekho.

MCM ko interval DP kyun kehte hain?

State

m [i] [j]

chain ka ek contiguous interval

[i, j]

describe karta hai, aur transitions us interval ko ek inner point pe split karte hain. Yahi shape Optimal Binary Search Tree aur Burst Balloons mein bhi aata hai.

Hum sirf ek single index ki jagah pair

(i, j)

pe memoize kyun nahi kar sakte?

Ek subproblem ek contiguous sub-chain hai, jiske liye dono endpoints chahiye. Ek index

A_{2} A_{3}

aur

A_{2} A_{3} A_{4}

mein distinguish nahi kar sakta.

Burst Balloons last balloon burst fix kyun karta hai jabki MCM last multiplication fix karta hai?

Dono cases mein fixed element dono remaining sides ko independent banata hai. MCM mein split point left/right chains ko cleanly separate karta hai; Burst Balloons mein sirf last-burst balloon independent sub-intervals chodta hai.

Edge cases

Single matrix (

n = 1

p = [a, b]

) ke liye MCM kya return karta hai?

Zero. Sirf

m [1] [1] = 0

hai; length loop for L in 2..n kabhi run nahi hota, isliye koi kaam nahi hota.

Do matrices (

n = 2

) ke liye kitne splits try kiye jaate hain aur cost kya hai?

Exactly ek split (

k = 1

), jo cost

p_{0} p_{1} p_{2}

deta hai. Koi choice nahi hai, isliye "optimization" trivial hai.

Agar chain mein do matrices square aur equal-sized hain, toh kya parenthesization phir bhi matter karta hai?

Poori chain ke liye phir bhi matter kar sakta hai, lekin identical

b \times b

matrices ke ek run mein har pairwise combine cost

b^{3}

hoti hai, isliye unke beech mein order neutral hota hai — differences sirf neighbouring non-equal dimensions ke through aate hain.

Agar kisi dimension ka size

1

ho (row/column vector, e.g.

p_{k} = 1

), toh kya kuch alag hoga?

Ye fully valid hai; ye simply us boundary ke through combines ko sasta banata hai (

p_{i - 1} \cdot 1 \cdot p_{j}

), jo aksar optimal split ko us

k

ki taraf le jaata hai. Koi special-casing nahi chahiye.

Kya

m [i] [j]

kabhi negative ho sakta hai ya empty chain se benefit ho sakta hai?

Nahi. Saari dimensions positive hain, isliye har combine cost positive hai; costs sirf badhti hain. Empty-chain case nahi hai kyunki split

i \leq k < j

enforce karta hai.

Kya optimal split point

k

hamesha unique hota hai?

Nahi. Ties ho sakti hain jahan do splits same minimum cost dein. Koi bhi ek optimal hai;

s [i] [j]

sirf wahi record karta hai jo tumhari comparison ne rakh liya.

Recall One-line self-test

Sab kuch cover karo: (1) Combine cost formula kya hai? (2) Table fill karne ka order kya hai? (3) Greedy kyun nahi? Combine cost ::: $p_{i - 1} p_{k} p_{j}$ . Fill order ::: increasing chain length $L = j - i + 1$ . Not greedy ::: locally sasta split costly sub-chains force kar sakta hai; sirf saare splits try karna safe hai.

Connections

Matrix Chain Multiplication (MCM) — parent derivation
Dynamic Programming — optimal substructure + overlapping subproblems
Catalan Numbers — parenthesization count $C_{n - 1}$
Optimal Binary Search Tree · Burst Balloons — same interval-DP shape
Memoization vs Tabulation · Time Complexity Analysis

Question bank — DP problems — matrix chain multiplication

True or false — justify