Matrix chain multiplication
Where to put the brackets in a product of matrices so it costs the fewest multiplications. Each interval tries every split point.
Why the order matters
Multiplying a p × q matrix by a q × r matrix costs p · q · r scalar multiplications. Matrix multiplication is associative, so a chain A·B·C can be computed as (A·B)·C or A·(B·C), and the costs can differ enormously. With A 10 × 30, B 30 × 5 and C 5 × 60:
- (A·B)·C costs 10·30·5 + 10·5·60 = 1,500 + 3,000 = 4,500;
- A·(B·C) costs 30·5·60 + 10·30·60 = 9,000 + 18,000 = 27,000.
The chain is given as a list of dimensions d: matrix i is d[i] × d[i + 1].
The interval recurrence with a split point
Recurrence
cost(i, j)
- fewest multiplications to compute matrices i..j =
- min over the last split k, i ≤ k < j, of cost(i, k) + cost(k + 1, j) + d[i] · d[k + 1] · d[j + 1].
base cases
- cost(i, i) = 0: a single matrix needs no work.
This "try every split, combine the two sides, pay for joining them" shape is the template for interval DP: burst balloons, merging stones, cutting a stick and optimal binary search trees all follow it.
A 10×30, B 30×5, C 5×60. Intervals by length; each tries every split point.
-
Step 1 / 7
Base cases filled first.
-
Step 2 / 7
A single matrix: 0.
-
Step 3 / 7
A single matrix: 0.
-
Step 4 / 7
A single matrix: 0.
-
Step 5 / 7
AB: split after A: 1500. Best 1500.
-
Step 6 / 7
BC: split after B: 9000. Best 9000.
-
Step 7 / 7
ABC: split after A: 27000; split after B: 4500. Best 4500. cost(A..C) = 4500, splitting after B: (A·B)·C.
Implementation
In six languages:
def matrix_chain(dims):
n = len(dims) - 1 # number of matrices
cost = [[0] * n for _ in range(n)] # cost[i][j]: matrices i..j
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
cost[i][j] = min(cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
for k in range(i, j)) # k: where the last multiplication splits
return cost[0][n - 1]#include <algorithm>
#include <climits>
#include <vector>
long long solve(const std::vector<int>& dims) {
const int n = dims.size() - 1;
std::vector<std::vector<long long>> cost(n, std::vector<long long>(n, 0));
for (int len = 2; len <= n; ++len)
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
cost[i][j] = LLONG_MAX;
for (int k = i; k < j; ++k) // the last split
cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k + 1][j] + (long long)dims[i] * dims[k + 1] * dims[j + 1]);
}
return cost[0][n - 1];
}class Solution {
public long matrixChain(int[] dims) {
int n = dims.length - 1;
long[][] cost = new long[n][n];
for (int len = 2; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
cost[i][j] = Long.MAX_VALUE;
for (int k = i; k < j; k++) // the last split
cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k + 1][j] + (long) dims[i] * dims[k + 1] * dims[j + 1]);
}
return cost[0][n - 1];
}
}function matrixChain(dims) {
const n = dims.length - 1;
const cost = Array.from({ length: n }, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
cost[i][j] = Infinity;
for (let k = i; k < j; k++) // the last split
cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]);
}
return cost[0][n - 1];
}fn solve(dims: &[i64]) -> i64 {
let n = dims.len() - 1;
let mut cost = vec![vec![0i64; n]; n];
for len in 2..=n {
for i in 0..=n - len {
let j = i + len - 1;
cost[i][j] = (i..j) // k: the last split
.map(|k| cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1])
.min()
.unwrap();
}
}
cost[0][n - 1]
}import Data.Array
solve :: [Int] -> Int
solve dims = cost ! (0, n - 1)
where
n = length dims - 1
d = listArray (0, n) dims
-- a lazy table: every interval refers only to shorter ones
cost = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
go i j
| i >= j = 0
| otherwise = minimum [cost ! (i, k) + cost ! (k + 1, j) + d ! i * d ! (k + 1) * d ! (j + 1) | k <- [i .. j - 1]]The same code is the reference solution to The cheapest order to multiply matrices, where it is compiled and run against the tests in all six languages.
n² intervals, up to n split points each. Recording the best split per interval lets you print the brackets.