Matrix Chain Multiplication
Given matrix dimensions where matrix i is dims[i-1] x dims[i], find the fewest scalar multiplications needed to multiply the whole chain.
- 2 <= dims.length <= 100
- 1 <= dims[i] <= 500
- Matrix i has shape dims[i-1] x dims[i]
Intuition
Matrix chain multiplication finds the cheapest way to parenthesise a chain of matrix multiplications. Matrix multiplication is associative, so every parenthesisation produces the same matrix — but the cost differs enormously, sometimes by orders of magnitude.
Multiplying an a×b matrix by a b×c matrix costs a·b·c scalar multiplications. Chain three matrices and the two groupings can differ by a factor of hundreds.
The framing that makes this tractable is the same one behind Burst Balloons: ask which multiplication happens last, not first. If the final multiplication splits the chain at position k, then everything left of k has already been reduced to one matrix and everything right of it likewise:
- The two sides are independent subproblems, and the final multiplication's cost is fixed by the chain's outer dimensions and the split point.
So dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + dims[i−1]·dims[k]·dims[j]. Trying every k covers every parenthesisation without enumerating any.
The filling order is where implementations go wrong. Each cell reads shorter intervals, so the table must be filled by increasing interval length — not row by row. Row-major order reads cells that have not been computed yet and silently produces wrong answers.
The dimensions array is off-by-one prone: matrix i is dims[i−1] × dims[i], so the cost term uses three entries that are easy to misalign.
Interval DP: the answer for a range depends on splitting it at every interior point and combining two smaller ranges. Iterating by increasing span guarantees both halves are already computed. Any problem phrased as "optimally parenthesise / partition a sequence" has this shape.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n³) time and O(n²) space.
Note that only the cost varies
Associativity means every parenthesisation yields the same product. Only the scalar multiplication count differs, which is why this is an optimisation problem rather than a correctness one.
Ask which multiplication is last
Fixing the last multiplication splits the chain into two independent halves whose costs are already known. Asking which is first fails, because the halves would still interact — the same reversal that solves Burst Balloons.
Define the state over intervals
dp[i][j] is the minimum cost to reduce matrices i through j to a single matrix. A single matrix needs no work, so the diagonal is zero.
Try every split point
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]. The last term is the cost of the final multiplication, whose dimensions are fixed by the interval's ends and the split.
Fill by increasing interval length
Every cell reads shorter intervals, so iterate span from 2 to n and slide i across. Filling row by row reads cells that have not been computed yet — a wrong answer that looks plausible.
Mind the dimensions indexing
Matrix i has shape dims[i-1] × dims[i], so the cost term touches three entries that are easy to misalign. An off-by-one here prices every multiplication wrongly while still producing a number.
Cost of the interval DP
There are O(n²) intervals each trying O(n) splits, giving O(n³) time and O(n²) space — the characteristic bound for interval DP, shared with Burst Balloons.
Solution & live demo
Common pitfalls
Iterating by i and j rather than by span
for i in range(1, n+1):
for j in range(i+1, n+1):for span in range(2, n + 1):
for i in range(1, n - span + 2):
j = i + span - 1dp[i][j] needs dp[i][k] and dp[k+1][j], both strictly shorter intervals. Plain nested loops over i and j read cells that haven't been filled yet, so the table is built from zeros.
Getting the cost formula's dimensions wrong
dims[i] * dims[k] * dims[j]
dims[i - 1] * dims[k] * dims[j]
Matrix i has dimensions dims[i-1] × dims[i], so the product of blocks i..k and k+1..j costs dims[i-1] × dims[k] × dims[j]. Using dims[i] shifts every factor and silently produces a plausible wrong number.
Letting k reach j
for k in range(i, j + 1):
for k in range(i, j):
The split puts i..k on the left and k+1..j on the right, so k = j leaves the right side empty and reads dp[j+1][j]. The last valid split point is j - 1.
Edge cases
dp[1][1] = 0 — nothing to multiply.
Exactly one split exists, so the answer is the single product dims[0]·dims[1]·dims[2].
The result is a multiplication count; the matrix product itself is identical under every parenthesisation.