Chain Matrix Multiplication

CMM

Pattern · interval + split point (the canonical one) Core DP2 lecture topic O(n³) 7difficulty

Question — exam style

You are given a chain of n matrices A₁, A₂, …, Aₙ to be multiplied together. Matrix multiplication is associative, so the order in which you multiply doesn't change the result — but it dramatically changes the cost. Multiplying a p × q matrix by a q × r matrix takes p·q·r scalar multiplications. The dimensions are given by an array m[0..n], where matrix Aᵢ has dimensions m[i−1] × m[i]. Design a dynamic-programming algorithm for the following task.

Input:Dimension array m[0], m[1], …, m[n] (so Aᵢ is m[i−1] × m[i]).

Output:The minimum number of scalar multiplications needed to compute A₁·A₂·⋯·Aₙ over all parenthesizations.

Getting fundamental clarity on CMM read this first

1 What the problem is really about — a concrete feel

Forget the formula. The result of A₁·A₂·A₃ is the same no matter how you group it, but the work is not. Take three matrices: A₁ (10×100), A₂ (100×5), A₃ (5×50).

Group as (A₁ A₂) A₃

A₁A₂ costs 10·100·5 = 5,000 → gives a 10×5.
Then ×A₃: 10·5·50 = 2,500.
Total 7,500.

Group as A₁ (A₂ A₃)

A₂A₃ costs 100·5·50 = 25,000 → gives a 100×50.
Then A₁×: 10·100·50 = 50,000.
Total 75,000.

Same answer matrix, 10× the work depending on where you put the parentheses. CMM asks: over all ways to parenthesize, what's the cheapest? That's it. The whole problem is "choose the multiplication order."

2 The one idea that unlocks the recurrence: the LAST multiplication

Here's the leap. Any full parenthesization of A₁·⋯·Aₙ, whatever it looks like inside, ends with one final multiplication that combines two already-computed pieces: a left block A₁·⋯·Aₖ and a right block Aₖ₊₁·⋯·Aₙ, for some split point k.

Every parenthesization is defined by where its outermost split is. If you knew the best k, the problem would break into two independent smaller chains — exactly the same kind of problem — plus the cost of that one last multiply.

You don't know the best k, so you try every possible split k = i, i+1, …, j−1 and take the cheapest. That "try every split point of a range" move is the signature of every interval DP.

3 Why the subproblem must be a WINDOW, not a prefix

When you split at k, the right block is Aₖ₊₁·⋯·Aⱼ — a chain that starts in the middle. A prefix table T(i) ("best for the first i matrices") can't describe it. You need both endpoints: C(i, j) = best cost for the sub-chain from i to j. That's why CMM is 2-D over a range, and why the answer sits at C(1, n) (the whole chain) rather than at a corner like C(n).

4 Decoding the cost term `m[i−1]·m[k]·m[j]`

This is the part people memorize without understanding — let's fix that. After you've computed the two blocks, you have:

Left block Aᵢ·⋯·Aₖ → its result is a matrix of size m[i−1] × m[k] (rows come from the first matrix Aᵢ, columns from the last matrix Aₖ).
Right block Aₖ₊₁·⋯·Aⱼ → result size m[k] × m[j].

Multiplying those two final results — a (m[i−1] × m[k]) by a (m[k] × m[j]) — costs exactly m[i−1] · m[k] · m[j] scalar multiplications. That's the price of the one last multiply, and it's why the term looks the way it does: it reads off the outer dimensions of the two blocks (m[i−1] and m[j]) and the shared inner dimension where they meet (m[k]).

So the recurrence reads: cost of the whole range = (best cost of left block) + (best cost of right block) + (cost of the single multiply that joins them), minimized over every place k you could put that split.

5 How to approach ANY problem that smells like CMM

The exam won't say "matrices." It'll say merge / combine / parenthesize / split a range and pay a cost to join the pieces. Your approach, every time:

Spot the tell: you're combining adjacent items in a sequence, and the cost of a merge depends on the two pieces being merged (their boundary/size/value). Order matters. → interval DP.
Define C(i,j) = best cost to fully process the sub-range from i to j.
Split on k: the last operation joins [i..k] with [k+1..j]. Cost = C(i,k) + C(k+1,j) + (cost to merge those two). Minimize over k.
Base case: a single item costs 0 (nothing to combine): C(i,i)=0.
Fill order: by increasing range length, because C(i,j) needs strictly-shorter ranges. Answer at C(1,n).

Re-skins you might see: string/rod cutting where a cut costs the piece's length (DPV 6.9), minimum-cost triangulation of a polygon (DPV 6.12), "merge stones/piles" where merging costs the combined size. All are CMM with a different merge-cost term.

Model answer

4-part format

aSubproblem in words

C(i, j) = the minimum number of scalar multiplications needed to compute the sub-chain product Aᵢ · Aᵢ₊₁ · ⋯ · Aⱼ, for 1 ≤ i ≤ j ≤ n.

A window/interval subproblem: indexed by both endpoints of a contiguous sub-chain. Recall Aₚ·⋯·A_q has result dimensions m[p−1] × m[q].

bRecurrence math only, with base case + bounds

C(i, i) = 0 for 1 ≤ i ≤ n C(i, j) = min{ C(i, k) + C(k+1, j) + m[i-1]·m[k]·m[j] : i ≤ k ≤ j-1 } for 1 ≤ i < j ≤ n

Choose the split point k where the final multiplication happens. The left block [i..k] and right block [k+1..j] are each solved optimally; joining their results (a m[i−1]×m[k] by a m[k]×m[j]) costs m[i−1]·m[k]·m[j]. Try all k, take the min. All referenced cells are strictly shorter ranges — well-defined, no self-reference.

cImplementation analysis

(1) # of subproblems

O(n²)

(2) Time to fill table

O(n³) — O(n) splits per cell

(3) Where answer is extracted

C(1, n)

(4) Time to extract

O(1)

Optional pseudocode not required by Ed #9

A mechanical translation. Outer loop over chain length is what guarantees smaller ranges are filled first — the #1 CMM trap.

function ChainMatrix(m[0..n]):
    for i = 1 to n: C[i][i] = 0
    for len = 2 to n:                     # chain length
        for i = 1 to n-len+1:
            j = i + len - 1
            C[i][j] = ∞
            for k = i to j-1:              # split point
                cost = C[i][k] + C[k+1][j] + m[i-1]*m[k]*m[j]
                C[i][j] = min(C[i][j], cost)
    return C[1][n]

The three CMM traps that cost points

1. Fill order: you must fill by increasing chain length (diagonal by diagonal), never row-major — a cell depends on shorter ranges below and to its left. 2. The cost term: it's m[i−1]·m[k]·m[j] — the left dimension is m[i−1], not m[i] (off-by-one is the classic error). 3. Don't drop the +cost: writing just min{C(i,k)+C(k+1,j)} without the merge term is the single biggest credit-loss.

Dimension indexing — get this straight

The dimension array is m[0..n] — that's n+1 numbers for n matrices. Matrix Aᵢ is m[i−1] × m[i], so consecutive matrices share a dimension (that's what makes them multipliable). The whole chain's result is m[0] × m[n]. A missing or shifted dimension breaks every cost term.

✎

Try it yourself

worked example + self-test

C(i,i)=0; C(i,j)=min_k{C(i,k)+C(k+1,j)+m[i−1]·m[k]·m[j]}. Answer C(1,n).

Worked min-over-k shown

m = [10, 20, 5, 30, 15] → A₁=10×20, A₂=20×5, A₃=5×30, A₄=30×15

Length 2 (one k each): C(1,2) = 10·20·5 = 1000 C(2,3) = 20·5·30 = 3000 C(3,4) = 5·30·15 = 2250 Length 3 (min over k): C(1,3): k=1 → C(2,3)+10·20·30 = 3000+6000 = 9000 k=2 → C(1,2)+10·5·30 = 1000+1500 = 2500 ← min C(2,4): k=2 → C(3,4)+20·5·15 = 2250+1500 = 3750 ← min k=3 → C(2,3)+20·30·15 = 3000+9000 = 12000 Length 4: C(1,4): k=1 → C(2,4)+10·20·15 = 3750+3000 = 6750 k=2 → C(1,2)+C(3,4)+10·5·15 = 1000+2250+750 = 4000 ← min k=3 → C(1,3)+10·30·15 = 2500+4500 = 7000 Final table (upper triangle): j=1 j=2 j=3 j=4 i=1 0 1000 2500 4000 i=2 . 0 3000 3750 i=3 . . 0 2250 i=4 . . . 0

Answer: C(1,4) = 4000 scalar multiplications. Optimal parenthesization: ((A₁A₂)(A₃A₄)).

Self-test fill by chain length, then reveal

m = [5, 10, 3, 12, 5] → A₁=5×10, A₂=10×3, A₃=3×12, A₄=12×5

Reveal answer

C(1,4) = 405, optimal parenthesization ((A₁A₂)(A₃A₄)). (For contrast, (A₁((A₂A₃)A₄)) costs 580 — a genuine difference, not a tie.)