DPAlgorithmaka MCM, matrix chain ordering, optimal parenthesization

Matrix Chain Multiplication

Choose the parenthesization of a matrix product that minimizes scalar multiplications — the archetypal interval DP.

▶ VisualizePattern: Dynamic ProgrammingPractice (2)
Progress

Overview

Multiplying matrices A₁ × A₂ × … × Aₙ gives the same result regardless of parenthesization (associativity), but the cost differs enormously. Multiplying a p×q by a q×r matrix costs p·q·r scalar multiplications. Given dimensions d[0..n] where Aᵢ is d[i-1] × d[i], find the parenthesization with minimum total cost.

This is the canonical interval DP (see Interval (Range) DP): the state is a contiguous range of matrices, the transition tries every split point inside it, and ranges are solved in increasing length. Burst Balloons, optimal BST, and polygon triangulation share the exact structure.

interval DP2D DPO(n³)split pointparenthesization

Intuition

A mental model before the formal terms.

Three matrices with dimensions 10×30, 30×5, 5×60. (A₁A₂)A₃ costs 10·30·5 + 10·5·60 = 1500 + 3000 = 4500. A₁(A₂A₃) costs 30·5·60 + 10·30·60 = 9000 + 18000 = 27000. Same result, six times the work. The best order shrinks the "middle" dimension early.

For a chain, whatever you do, there is one *last* multiplication that joins a left group and a right group. If you knew where that split was, each side would be an independent, smaller chain problem. You do not know it, so try every split and keep the cheapest — but store each range's answer so the same sub-chain is never solved twice.

How it works

  1. State: dp[i][j] = minimum cost to multiply matrices Aᵢ … Aⱼ (1-indexed), whose product is d[i-1] × d[j].
  2. Transition: dp[i][j] = min over k in [i, j-1] of dp[i][k] + dp[k+1][j] + d[i-1]·d[k]·d[j] — cost of the left group, the right group, and the final multiplication of a d[i-1]×d[k] by a d[k]×d[j].
  3. Base case: dp[i][i] = 0 — a single matrix needs no multiplication.
  4. Iteration order: by increasing interval length len = 2..n; for each i, j = i + len - 1. Every dp[i][k] and dp[k+1][j] is a strictly shorter interval, so it is already filled. Top-down recursion on (i, j) with memoization avoids thinking about the order.
  5. Answer location: dp[1][n]. Store the best k in split[i][j] to print the parenthesization recursively.
  6. Space optimization: none of the usual rolling tricks apply — dp[i][j] needs arbitrary shorter intervals, not just an adjacent row. The table is O(n²); only the upper triangle is used.

Why it works

Optimal substructure: in an optimal parenthesization of Aᵢ…Aⱼ, the outermost multiplication splits the chain at some k. The parenthesization of Aᵢ…Aₖ inside it must itself be optimal — if a cheaper one existed, substituting it would lower the total without affecting the right side or the final multiplication cost (which depends only on d[i-1], d[k], d[j]). Same for the right side. Minimizing over all k therefore finds the optimum.

Overlapping subproblems: the number of parenthesizations is the Catalan number C(n-1) (exponential), but there are only n(n+1)/2 intervals. Each interval does O(n) work over splits, giving O(n³).

Processing by increasing length is a valid topological order of the dependency DAG because every dependency is a proper sub-interval.

Recognition

How to tell a problem wants this.

  • A sequence where the cost of combining a range depends on a split point inside it and the range boundaries.
  • "Minimum cost to parenthesize / merge / cut / remove" over a contiguous sequence; n ≤ 500 (cubic is fine).
  • Boundary elements stay fixed while the interior is resolved — hallmark of interval DP.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

10
0
30
1
5
2
60
3
A1A2A3
A10··
A2·0·
A3··0
1/9A1..A3 have shapes 10×30, 30×5, 5×60. A single matrix needs 0 multiplications, so the diagonal is 0. Only the upper triangle (i ≤ j) is used.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Matrix Chain Multiplication →
1dp[i][i] = 0
2for len in 2 .. n:
3  for i in 1 .. n-len+1: j = i+len-1
4    dp[i][j] = ∞
5    for k in i .. j-1:
6      cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
7      if cost < dp[i][j]: dp[i][j] = cost; split[i][j] = k
8return dp[1][n]
Variables
n3
Complexity
best O(n³)
avg O(n³)
worst O(n³)
space O(n²)
Speed

Pseudocode

1dp[i][i] = 0 for all i
2for len in 2..n:
3  for i in 1..n-len+1:
4    j = i + len - 1; dp[i][j] = INF
5    for k in i..j-1:
6      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + d[i-1]*d[k]*d[j])
7return dp[1][n]

Implementations

1import math
2 
3# Matrix chain multiplication: choose the parenthesisation that minimises
4# scalar multiplications. dims has n+1 entries: matrix i is dims[i] x dims[i+1].
5# This is the archetypal interval DP — solve short ranges first, and every
6# longer range is a split into two already-solved halves.
7 
8 
91 · dp[i][j] = min cost to multiply matrices i..j; split[i][j] records where
10def matrix_chain_order(dims: list[int]) -> tuple[int, list[list[int]]]:
11    n = len(dims) - 1  # number of matrices
12    if n <= 0:
13        return 0, []
14    dp = [[0] * n for _ in range(n)]
15    split = [[-1] * n for _ in range(n)]
16 
172 · Grow by chain length: length 1 costs 0, so start at 2
18    for length in range(2, n + 1):
19        for i in range(n - length + 1):
20            j = i + length - 1
21            best = math.inf
22            best_k = -1
233 · Try every split point; both halves are already final
24            for k in range(i, j):
25                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
26                if cost < best:
27                    best, best_k = cost, k
28            dp[i][j] = int(best)
29            split[i][j] = best_k
30    return dp[0][n - 1], split
31 
32 
334 · The split table reconstructs the parenthesisation
34def build_parens(split: list[list[int]], i: int, j: int) -> str:
35    if i == j:
36        return f"A{i}"
37    k = split[i][j]
38    return f"({build_parens(split, i, k)}{build_parens(split, k + 1, j)})"
39 
40 
415 · Why order matters: the same product can cost wildly different amounts
42def cost_of_left_to_right(dims: list[int]) -> int:
43    n = len(dims) - 1
44    total = 0
45    rows = dims[0]
46    for i in range(1, n):
47        total += rows * dims[i] * dims[i + 1]
48        # rows stays dims[0] because the accumulated product keeps its row count
49    return total
Walkthrough
  1. [[0] * n for _ in range(n)] builds n distinct rows; [[0] * n] * n would alias one row n times — the single most common Python 2D-array bug.
  2. best = math.inf starts the inner minimisation; the final int(best) converts back, since math.inf is a float and the costs are integers.
  3. Accumulating into a local best and only then writing dp[i][j] avoids repeatedly indexing the table inside the innermost loop.
  4. Python integers are unbounded, so the triple product dims[i] * dims[k+1] * dims[j+1] is always exact regardless of matrix size.
  5. f"A{i}" and the nested f-string in build_parens produce the bracketing without concatenation.
Complexity (this implementation)
time O(n^3) · space O(n^2)

The triple loop is pure Python, so this is one of the slower entries in the group — functools.lru_cache on a recursive form is often more readable at the same cost.

Language notes
  • [[0] * n] * n aliases; the list comprehension is the fix, and this bug appears in every 2D DP written in Python.
  • math.inf is a float, so mixing it into an integer table needs the int() conversion — using a large integer sentinel avoids that entirely.
  • functools.lru_cache on a recursive cost(i, j) expresses interval DP very naturally, at the cost of O(n^2) cache entries and recursion depth O(n).
  • numpy does not help here: the recurrence is inherently sequential over increasing lengths.
Common mistakes in this language
  • Using [[0] * n] * n and having every row alias the same list.
  • Leaving math.inf in an integer table, so dp[i][j] is a float and comparisons downstream become float comparisons.
  • Writing the recursive form without lru_cache, which is exponential.
Language differences that matter here
  • Building a 2D table safely is the shared trap, and it has the same shape in two languages: [[0] * n] * n in Python and new Array(n).fill(new Array(n)) in JS/TS both alias one row; C++ std::vector<std::vector<T>>(n, std::vector<T>(n)) value-initialises n distinct rows.
  • The infinity sentinel: JS/TS Infinity and Python math.inf compare and saturate cleanly, while C++ needs LLONG_MAX and the discipline never to add to it.
  • Overflow on the triple product: real in C++ without long long, silent past 2^53 in JS/TS, and impossible in Python.
  • String building for the reconstruction: C++ concatenation (or std::format), JS/TS template literals, and Python f-strings — the latter two nest cleanly, which matters for a recursive bracketing.

Complexity

Best
O(n³)
Average
O(n³)
Worst
O(n³)
Space
O(n²)

Hu–Shing solves MCM specifically in O(n log n), but the cubic interval DP is the general template.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Optimal order of associative binary combinations over a sequence where combination cost depends on the operands' "shape".
  • Any interval DP with a split point: Burst Balloons, Minimum Cost to Cut a Stick, Optimal BST, polygon triangulation, boolean parenthesization.
  • n up to a few hundred.
Avoid it when
  • The combination order does not affect cost (e.g. summing numbers) — nothing to optimize.
  • n ≥ 5000 — cubic is too slow; look for Knuth optimization (quadrangle inequality) or a problem-specific O(n log n) method.
  • The "split" is not contiguous (subset-based rather than interval-based) — that is Bitmask DP territory.

Alternatives

Interval (Range) DPDivide and ConquerBitmask DP

Common mistakes

  • Iterating i and j in plain row-major order — dp[k+1][j] for k+1 > i is not yet computed. Iterate by interval length (or use memoized recursion).
  • Off-by-one in the dimension array: matrix i is d[i-1] × d[i], so n = len(d) - 1.
  • Using int for costs: 500³ intermediate products overflow 32-bit.
  • In Burst Balloons, choosing the *first* balloon to burst instead of the *last* — the interval boundaries must remain fixed while the interior is solved.

Interview patterns

  • Matrix Chain Order: minimum multiplication cost and the parenthesization.
  • Burst Balloons: dp[i][j] = max over k of dp[i][k] + dp[k][j] + nums[i]·nums[k]·nums[j] with sentinel 1s.
  • Minimum Cost to Cut a Stick / Minimum Score Triangulation of Polygon.
  • Palindrome Partitioning II and "remove boxes" — interval DP with extra state.
Interview questions on this
Mock interviews

Example problems

Burst BalloonshardMatrix Chain Multiplicationhard