DP problems — matrix chain multiplication

WHAT is the problem?

WHY the dimension array? Because the contents of the matrices don't matter — only the cost does, and cost depends only on dimensions.

WHY does parenthesization matter? (worked motivation)

Take $A_1(10\times 100),\ A_2(100\times 5),\ A_3(5\times 50)$ , i.e. $p=[10,100,5,50]$ .

$(A_1A_2)A_3$ : $10\cdot100\cdot5 + 10\cdot5\cdot50 = 5000 + 2500 = \mathbf{7500}$
$A_1(A_2A_3)$ : $100\cdot5\cdot50 + 10\cdot100\cdot50 = 25000 + 50000 = \mathbf{75000}$

HOW to derive the recurrence (from scratch)

Key insight: Any full parenthesization of $A_i\cdots A_j$ has a last multiplication. That last multiply splits the chain at some point $k$ : $(A_i\cdots A_k)\,(A_{k+1}\cdots A_j)$

The left block produces a $p_{i-1}\times p_k$ matrix.
The right block produces a $p_k\times p_j$ matrix.
Combining them costs $p_{i-1}\,p_k\,p_j$ .

WHY this decomposition works: every parenthesization has exactly one outermost split. If we knew the best split $k$ , the subproblems "best cost of left" and "best cost of right" are independent — this is optimal substructure.

Let $m[i][j]$ = minimum cost to multiply $A_i\cdots A_j$ .

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

Full worked example

Matrices with $p=[30,35,15,5,10]$ → $A_1(30\times35), A_2(35\times15), A_3(15\times5), A_4(5\times10)$ , so $n=4$ .

Length 2 chains (cost of pairs):

$m[1][2]=p_0p_1p_2=30\cdot35\cdot15=15750$ — Why? only one split $k=1$ .
$m[2][3]=35\cdot15\cdot5=2625$
$m[3][4]=15\cdot5\cdot10=750$

Length 3 chains:

$m[1][3]=\min\begin{cases}k{=}1: m[1][1]+m[2][3]+p_0p_1p_3=0+2625+30\cdot35\cdot5=2625+5250=7875\\ k{=}2: m[1][2]+m[3][3]+p_0p_2p_3=15750+0+30\cdot15\cdot5=15750+2250=18000\end{cases}=\mathbf{7875}\ (k{=}1)$

Why this step? We compare splitting after $A_1$ vs after $A_2$ ; the cheaper is splitting at $k=1$ .
$m[2][4]=\min\begin{cases}k{=}2: 0+750+35\cdot15\cdot10=750+5250=6000\\ k{=}3: 2625+0+35\cdot5\cdot10=2625+1750=4375\end{cases}=\mathbf{4375}\ (k{=}3)$

Length 4 chain (the answer): $m[1][4]=\min\begin{cases}k{=}1: m[1][1]+m[2][4]+p_0p_1p_4=0+4375+30\cdot35\cdot10=4375+10500=14875\\ k{=}2: m[1][2]+m[3][4]+p_0p_2p_4=15750+750+30\cdot15\cdot10=16500+4500=21000\\ k{=}3: m[1][3]+m[4][4]+p_0p_3p_4=7875+0+30\cdot5\cdot10=7875+1500=9375\end{cases}$ $=\mathbf{9375}\quad (k=3)$

Common mistake Steel-manning the common errors

Mistake 1: "Greedy — always split where the dimension is smallest." Why it feels right: small dimensions look cheap. Why it's wrong: a locally cheap split can force an expensive combine later. The 7500 vs 75000 example shows greed fails. Fix: you must try all splits (DP).

Mistake 2: Off-by-one with the dimension array. Why it feels right: people index $A_i$ as $p_i\times p_{i+1}$ . Why it's wrong/confusing: the standard convention is $A_i = p_{i-1}\times p_i$ , and the split cost is $p_{i-1}p_k p_j$ (not $p_i p_k p_j$ ). Fix: memorize " $A_i$ uses $p_{i-1}$ and $p_i$ ".

Mistake 3: Filling the table row-by-row. Why it feels right: that's how we read tables. Why it's wrong: $m[i][j]$ needs shorter chains that may not be computed yet. Fix: loop by chain length $L$ , not by $i$ .

Mistake 4: Counting additions instead of multiplications. Cost = scalar multiplications $=abc$ ; we ignore additions.

Recall Feynman: explain to a 12-year-old

Imagine you have to glue together a row of LEGO sheets, two at a time. Joining two sheets takes effort that depends on their sizes. The final big sheet is the same whichever order you glue, but some orders cost way less effort. MCM is just the smart plan: try every spot where you could make the last glue, remember the cheapest way to build each piece, and never re-solve the same piece twice.

Flashcards

What does matrix

A_i

's dimension equal in MCM convention?

p_{i-1}\times p_i

, using the dimension array

p[0..n]

What is the cost of multiplying an

a\times b

by a

b\times c

matrix?

a\cdot b\cdot c

scalar multiplications.

State the MCM recurrence.

m[i][j]=\min_{i\le k<j}(m[i][k]+m[k+1][j]+p_{i-1}p_k p_j)

, with

m[i][i]=0

Why try all split points

k

We don't know the optimal last multiplication; greedy fails, so try all and take the min (optimal substructure + overlapping subproblems).

What order do we fill the DP table?

By increasing chain length

L=j-i+1

(length 2 up to

n

), not row by row.

Time and space complexity of MCM DP?

Time

O(n^3)

(loops over L, i, k), space

O(n^2)

What is the cost of

A_1(10\times100),A_2(100\times5),A_3(5\times50)

(A_1A_2)A_3

A_1(A_2A_3)

7500 vs 75000 — same result, 10× difference.

How do you recover the actual parenthesization?

Store split point

s[i][j]=k

, then recurse on

[i,k]

and

[k+1,j]

Why does parenthesization not change the result matrix?

Matrix multiplication is associative.

What is the base case and why?

m[i][i]=0

because a single matrix needs no multiplication.

Connections

Dynamic Programming — optimal substructure + overlapping subproblems
Catalan Numbers — counts the parenthesizations $C_{n-1}$
Optimal Binary Search Tree — same "try every root/split" interval-DP pattern
Burst Balloons — interval DP where you fix the last element
Memoization vs Tabulation
Time Complexity Analysis — $O(n^3)$ from three nested loops

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Matrix Chain Multiplication ka core idea simple hai: jab tum bahut saari matrices ko multiply karte ho, toh answer matrix toh same rehta hai chahe tum kisi bhi order me brackets lagao (kyunki multiplication associative hai). Lekin kitni scalar multiplications lagti hain, woh order pe depend karta hai — aur farak 10x, 100x tak ho sakta hai. Ek $a\times b$ ko $b\times c$ se multiply karne ka cost hota hai $a\cdot b\cdot c$ . Bas yahi cost minimize karna hai.

Trick ye hai ki tum last multiplication pe socho. Poora chain $A_i \dots A_j$ ka last multiply kahin na kahin par split hota hai, point $k$ pe: left part banao, right part banao, phir dono ko jodo. Jodne ka cost $p_{i-1}\,p_k\,p_j$ . Humein nahi pata best $k$ kaunsa hai, isliye saare $k$ try karo aur minimum lo. Yahi recurrence hai: $m[i][j]=\min_k(m[i][k]+m[k+1][j]+p_{i-1}p_k p_j)$ , aur single matrix ka cost $0$ .

Greedy mat lagao — "sabse chhota dimension pe cut karo" wala idea galat hai, kyunki abhi sasta lagne wala cut baad me mehnga pad sakta hai. Isliye DP use karte hain. Table ko chain length L ke order me bharo (chhoti chains pehle), kyunki badi chain ko chhoti chains chahiye hoti hain. Time complexity $O(n^3)$ aati hai (L, i, k teen loops), space $O(n^2)$ .

Yaad rakhne ka jugaad: "Last cut, all spots, $p_{i-1}p_k p_j$ ." Aur split point ko $s[i][j]$ me store kar lo taaki actual bracket structure wapas bana sako. Exam aur interview dono me ye classic interval-DP problem hai — Optimal BST aur Burst Balloons bhi isi pattern pe chalte hain.

DP problems — matrix chain multiplication

WHAT is the problem?

WHY does parenthesization matter? (worked motivation)

HOW to derive the recurrence (from scratch)

Bottom-up algorithm

Full worked example

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections