Matrix Chain Multiplication

Interval DP that splits the chain Aᵢ … Aⱼ at every k, recurses on the two halves, and adds the cost p[i−1]·p[k]·p[j] for the final multiplication.

Problem

You are given a chain of n matrices A₁ · A₂ · A₃ · … · Aₙ that you want to multiply together. Matrix multiplication is associative (you can put parentheses anywhere) but not commutative (you cannot reorder), so the final answer is the same no matter how you parenthesize — but the number of scalar multiplications to get there can change a lot.

We describe the chain by an array p[0 … n] of dimensions: matrix Aᵢ has size p[i − 1] × p[i] (for i = 1 … n). For example, p = [10, 30, 5, 60] describes three matrices: A₁ (10×30), A₂ (30×5), A₃ (5×60).

Multiplying a (p × q) matrix with a (q × r) matrix takes p · q · r scalar multiplications and produces a (p × r) matrix.

Find the minimum total number of scalar multiplications over all ways to parenthesize the chain.

Tiny example. With p = [10, 30, 5, 60]:

((A₁ · A₂) · A₃): first A₁·A₂ costs 10·30·5 = 1500 and gives a 10×5 matrix; then (10×5) · (5×60) costs 10·5·60 = 3000. Total = 4500.
(A₁ · (A₂ · A₃)): first A₂·A₃ costs 30·5·60 = 9000 and gives a 30×60 matrix; then (10×30) · (30×60) costs 10·30·60 = 18000. Total = 27000.

Minimum is 4500.

DP recurrence relation

Meaning of the state. Let m(i, j) = minimum number of scalar multiplications to compute the product Aᵢ · Aᵢ₊₁ · … · Aⱼ (a chain of matrices from index i through j, inclusive), where 1 ≤ i ≤ j ≤ n. The result is a matrix of size p[i − 1] × p[j].

Idea in words. If i = j there is just one matrix and no multiplications are needed: m(i, i) = 0.

Otherwise, the last multiplication in any parenthesization splits the chain at some position k with i ≤ k < j, combining:

the left subchain Aᵢ · … · Aₖ — a matrix of size p[i − 1] × p[k] computed in m(i, k) multiplications, and
the right subchain Aₖ₊₁ · … · Aⱼ — a matrix of size p[k] × p[j] computed in m(k + 1, j) multiplications.

Multiplying those two together costs p[i − 1] · p[k] · p[j] more. We do not know the best k, so try every split and keep the smallest total:

Example

m(i, j) = min over k = i … j − 1 of

( m(i, k) + m(k + 1, j) + p[i − 1] · p[k] · p[j] )

Why this is correct. Every valid parenthesization has exactly one outermost split position k; trying all j − i choices covers them all, and for each fixed k the two sides must be parenthesized optimally (otherwise we could swap in a better one and lower the total).

DP memoization

Use a 2D table memo[1 … n][1 … n] with a sentinel like −1 for “not computed yet.” When asked for m(i, j):

If i == j, return 0 directly.
If memo[i][j] is set, return it.
Otherwise loop k = i … j − 1, recurse to get m(i, k) and m(k + 1, j), evaluate m(i, k) + m(k + 1, j) + p[i − 1] · p[k] · p[j], keep the min, store it in memo[i][j], and return.

There are O(n²) states (subchains (i, j)), and each one tries O(n) split points, so total work is O(n³) time. Space is O(n²) for the memo plus recursion depth at most n.

(To recover the best parenthesization itself, store the winning k for each (i, j) in a second table during the loop, then print recursively.)

DP base case

A single matrix needs no multiplication:

Example

m(i, i) = 0 for every i = 1 … n

Explanation. No work is needed to “compute” one matrix that already exists. Every recursion eventually reaches this case because each split produces strictly shorter subchains (the left side ends at k ≤ j − 1 and the right side starts at k + 1 ≥ i + 1).

Worked example

Take n = 4 matrices with dimensions array p = [30, 35, 15, 5, 10]. So the matrices are:

A₁: 30 × 35
A₂: 35 × 15
A₃: 15 × 5
A₄: 5 × 10

Fill m(i, j) by chain length L = j − i + 1, from short chains to long ones.

L = 1 (single matrices): m(1,1) = m(2,2) = m(3,3) = m(4,4) = 0.

L = 2 (one possible split each):

m(1, 2) = m(1,1) + m(2,2) + p[0]·p[1]·p[2] = 0 + 0 + 30·35·15 = 15750.
m(2, 3) = 0 + 0 + 35·15·5 = 2625.
m(3, 4) = 0 + 0 + 15·5·10 = 750.

L = 3 (two splits to try):

m(1, 3): split at k = 1 → m(1,1) + m(2,3) + p[0]·p[1]·p[3] = 0 + 2625 + 30·35·5 = 7875. Split at k = 2 → m(1,2) + m(3,3) + p[0]·p[2]·p[3] = 15750 + 0 + 30·15·5 = 18000. Min = 7875 (at k = 1).
m(2, 4): split at k = 2 → 0 + 750 + 35·15·10 = 6000. Split at k = 3 → 2625 + 0 + 35·5·10 = 4375. Min = 4375 (at k = 3).

L = 4 (three splits to try): m(1, 4):

k = 1: m(1,1) + m(2,4) + p[0]·p[1]·p[4] = 0 + 4375 + 30·35·10 = 14875.
k = 2: m(1,2) + m(3,4) + p[0]·p[2]·p[4] = 15750 + 750 + 30·15·10 = 21000.
k = 3: m(1,3) + m(4,4) + p[0]·p[3]·p[4] = 7875 + 0 + 30·5·10 = 9375 ← best.

So m(1, 4) = 9375. The best split is at k = 3, meaning the outermost grouping is ((A₁ · A₂ · A₃) · A₄), and inside that the best split for A₁ · A₂ · A₃ is at k = 1 giving (A₁ · (A₂ · A₃)). Final parenthesization: ((A₁ · (A₂ · A₃)) · A₄).

Pseudocode

Read MATRIX-CHAIN(i, j) as “the cheapest way to multiply the chain Aᵢ · … · Aⱼ.” The loop tries every position k where the last multiplication could split the chain, recursively prices the two halves, and adds p[i − 1] · p[k] · p[j] — the cost of combining the two resulting matrices. Indices i, j are 1-based.

1MATRIX-CHAIN(i, j, p, memo)       // min cost to multiply A_i · … · A_j
2  if i == j                       // one matrix → nothing to multiply
3    return 0
4  if memo[i][j] != UNKNOWN        // already solved? reuse the answer
5    return memo[i][j]
6  best = INFINITY
7  for k = i to j - 1              // try every split (A_i…A_k) · (A_k+1…A_j)
8    left  = MATRIX-CHAIN(i,     k, p, memo)        // best cost of left half
9    right = MATRIX-CHAIN(k + 1, j, p, memo)        // best cost of right half
10    cost  = left + right + p[i - 1] * p[k] * p[j]  // + final multiplication
11    best  = min(best, cost)
12  memo[i][j] = best
13  return best

Complexity

Time: O(n³) — there are O(n²) subchains and each tries O(n) split points. Space: O(n²) for the memo, plus recursion depth at most O(n).

Complexity Analysis

Time Complexity

O(n³)

Space Complexity

O(n²) for memo

Classic interval DP — fill in order of increasing chain length

Growth Rate Comparison

Problem

Multiplying a (p × q) matrix with a (q × r) matrix takes p · q · r scalar multiplications and produces a (p × r) matrix.

Find the minimum total number of scalar multiplications over all ways to parenthesize the chain.

Tiny example. With p = [10, 30, 5, 60]:

((A₁ · A₂) · A₃): first A₁·A₂ costs 10·30·5 = 1500 and gives a 10×5 matrix; then (10×5) · (5×60) costs 10·5·60 = 3000. Total = 4500.
(A₁ · (A₂ · A₃)): first A₂·A₃ costs 30·5·60 = 9000 and gives a 30×60 matrix; then (10×30) · (30×60) costs 10·30·60 = 18000. Total = 27000.

Minimum is 4500.

DP recurrence relation

Idea in words. If i = j there is just one matrix and no multiplications are needed: m(i, i) = 0.

Otherwise, the last multiplication in any parenthesization splits the chain at some position k with i ≤ k < j, combining:

the left subchain Aᵢ · … · Aₖ — a matrix of size p[i − 1] × p[k] computed in m(i, k) multiplications, and
the right subchain Aₖ₊₁ · … · Aⱼ — a matrix of size p[k] × p[j] computed in m(k + 1, j) multiplications.

Multiplying those two together costs p[i − 1] · p[k] · p[j] more. We do not know the best k, so try every split and keep the smallest total:

Example

m(i, j) = min over k = i … j − 1 of

( m(i, k) + m(k + 1, j) + p[i − 1] · p[k] · p[j] )

DP memoization

Use a 2D table memo[1 … n][1 … n] with a sentinel like −1 for “not computed yet.” When asked for m(i, j):

If i == j, return 0 directly.
If memo[i][j] is set, return it.
Otherwise loop k = i … j − 1, recurse to get m(i, k) and m(k + 1, j), evaluate m(i, k) + m(k + 1, j) + p[i − 1] · p[k] · p[j], keep the min, store it in memo[i][j], and return.

There are O(n²) states (subchains (i, j)), and each one tries O(n) split points, so total work is O(n³) time. Space is O(n²) for the memo plus recursion depth at most n.

(To recover the best parenthesization itself, store the winning k for each (i, j) in a second table during the loop, then print recursively.)

DP base case

A single matrix needs no multiplication:

Example

m(i, i) = 0 for every i = 1 … n

Worked example

Take n = 4 matrices with dimensions array p = [30, 35, 15, 5, 10]. So the matrices are:

A₁: 30 × 35
A₂: 35 × 15
A₃: 15 × 5
A₄: 5 × 10

Fill m(i, j) by chain length L = j − i + 1, from short chains to long ones.

L = 1 (single matrices): m(1,1) = m(2,2) = m(3,3) = m(4,4) = 0.

L = 2 (one possible split each):

m(1, 2) = m(1,1) + m(2,2) + p[0]·p[1]·p[2] = 0 + 0 + 30·35·15 = 15750.
m(2, 3) = 0 + 0 + 35·15·5 = 2625.
m(3, 4) = 0 + 0 + 15·5·10 = 750.

L = 3 (two splits to try):

m(1, 3): split at k = 1 → m(1,1) + m(2,3) + p[0]·p[1]·p[3] = 0 + 2625 + 30·35·5 = 7875. Split at k = 2 → m(1,2) + m(3,3) + p[0]·p[2]·p[3] = 15750 + 0 + 30·15·5 = 18000. Min = 7875 (at k = 1).
m(2, 4): split at k = 2 → 0 + 750 + 35·15·10 = 6000. Split at k = 3 → 2625 + 0 + 35·5·10 = 4375. Min = 4375 (at k = 3).

L = 4 (three splits to try): m(1, 4):

k = 1: m(1,1) + m(2,4) + p[0]·p[1]·p[4] = 0 + 4375 + 30·35·10 = 14875.
k = 2: m(1,2) + m(3,4) + p[0]·p[2]·p[4] = 15750 + 750 + 30·15·10 = 21000.
k = 3: m(1,3) + m(4,4) + p[0]·p[3]·p[4] = 7875 + 0 + 30·5·10 = 9375 ← best.

Pseudocode

1MATRIX-CHAIN(i, j, p, memo)       // min cost to multiply A_i · … · A_j
2  if i == j                       // one matrix → nothing to multiply
3    return 0
4  if memo[i][j] != UNKNOWN        // already solved? reuse the answer
5    return memo[i][j]
6  best = INFINITY
7  for k = i to j - 1              // try every split (A_i…A_k) · (A_k+1…A_j)
8    left  = MATRIX-CHAIN(i,     k, p, memo)        // best cost of left half
9    right = MATRIX-CHAIN(k + 1, j, p, memo)        // best cost of right half
10    cost  = left + right + p[i - 1] * p[k] * p[j]  // + final multiplication
11    best  = min(best, cost)
12  memo[i][j] = best
13  return best

Complexity

Time: O(n³) — there are O(n²) subchains and each tries O(n) split points. Space: O(n²) for the memo, plus recursion depth at most O(n).

Complexity Analysis

Time Complexity

O(n³)

Space Complexity

O(n²) for memo

Classic interval DP — fill in order of increasing chain length