Dynamic Programming: Chain Matrix Multiplication

The purpose of this post is to show a fully worked-out example of Chain Matrix Multiplication using dynamic programming — a technique for breaking a big problem down into subproblems which are easier to solve.

If you prefer to read the post as a step-by-step walkthrough, use the slider below. Or scroll past it for the full contiguous version.

1.Motivation2.The Problem3.Dimension Table4.Chains of Length 2 & 35.Chains of Length 4 & 56.Final Answer

Motivation

The purpose of this post is to show a fully worked out example of Chain Matrix Multiplication using dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve.

Matrix multiplication is associative, meaning the order in which we parenthesize a chain of multiplications does not change the final result — but it dramatically changes the number of scalar multiplications needed.

For example, given matrices A (10×30), B (30×5), C (5×60):

• **(A × B) × C** → 10·30·5 + 10·5·60 = 1500 + 3000 = **4500 ops**
• **A × (B × C)** → 30·5·60 + 10·30·60 = 9000 + 18000 = **27000 ops**

Dynamic programming finds the optimal parenthesization efficiently.

---

The Full Walkthrough (Contiguous)

Motivation

Matrix multiplication is associative — the order we parenthesize doesn’t change the result, but it dramatically changes the cost. Dynamic programming finds the optimal parenthesization in O(n³) time.

The Problem

Five matrices M₁–M₅ with dimensions 5×10, 10×3, 3×12, 12×5, 5×50. We want the cheapest way to multiply them all together.

The recurrence:

cost(i, i)   = 0
cost(i, j)   = min over k in [i, j-1] of:
               cost(i, k) + cost(k+1, j) + p[i-1] * p[k] * p[j]

Building the Table

len	(i,j)	min cost
1	(1,1)–(5,5)	0
2	(1,2)=150, (2,3)=360, (3,4)=180, (4,5)=3000
3	(1,3)=330, (2,4)=210, (3,5)=930
4	(1,4)=405, (2,5)=1680
5	(1,5)=1655

Optimal Parenthesization

((M₁ × (M₂ × M₃)) × M₄) × M₅ at a cost of 1655 scalar multiplications.