Dynamic Programming8 min read

Matrix Chain Multiplication

The order you multiply matrices matters enormously — find the cheapest order
time:\(O(n^3)\)space:\(O(n^2)\)

Suppose you're organizing a road trip with multiple legs. The order you combine those legs doesn't change your final destination — but it can make a huge difference in how much fuel you burn. Matrix chain multiplication is exactly like this: no matter how you parenthesize A × B × C × D, the result is the same matrix. But the cost — the number of arithmetic operations — can vary by orders of magnitude.

Multiplying a (a×b) matrix by a (b×c) matrix costs a × b × c scalar multiplications and produces an (a×c) result.

A Concrete Example

Three matrices: A(10×30), B(30×5), C(5×60).

(A×B)×C: A×B costs 10×30×5 = 1,500 → (10×5); then ×C costs 10×5×60 = 3,000. Total: 4,500.

A×(B×C): B×C costs 30×5×60 = 9,000 → (30×60); then A× costs 10×30×60 = 18,000. Total: 27,000.

The first order is 6× cheaper! For longer chains, the gap grows much larger.

The DP State

Define dp[i][j] = minimum scalar multiplications to compute the product of matrices i through j. Dimensions are given as an array dim[] where matrix i has shape dim[i-1] × dim[i]. We want dp[1][n].

The Recurrence

For any split point k (i ≤ k < j), we first compute matrices i..k, then k+1..j, then multiply the two results:

dp[i][j] = min over k of: dp[i][k] + dp[k+1][j] + dim[i-1] × dim[k] × dim[j]

Base case: dp[i][i] = 0 (a single matrix needs no multiplication).

Fill Order: Short Chains First

dp[i][j] needs dp[i][k] and dp[k+1][j] — both shorter chains. This is a classic case of Interval DP. So fill by increasing chain length: l = 1 (base cases), then l = 2 (pairs), up to l = n. For each length, iterate over all valid starting positions i (with j = i + l - 1).

Recovering the Optimal Parenthesization

Store the best split point s[i][j] alongside dp[i][j]. Then recursively read the parenthesization: s[1][n] gives the top-level split; recurse into [1, s[1][n]] and [s[1][n]+1, n].

Note: The number of ways to parenthesize n matrices is the (n-1)th Catalan number — which grows exponentially. For n=10 matrices, there are 4,862 parenthesizations. DP finds the best one in \(O(n^3)\) instead of trying all of them.

Matrix Chain Multiplication — minimum cost

def matrix_chain(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0]*n for _ in range(n)]
    # fill by increasing chain length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]


# dims[i-1] x dims[i] is matrix i's shape
print(matrix_chain([10, 30, 5, 60]))   # 4500
print(matrix_chain([40, 20, 30, 10, 30]))  # 26000
Output
4500
26000

Complexity

⏱️ Time
\(O(n^2)\) intervals × \(O(n)\) split points per interval
Cubic \(O(n^3)\)
📊 Space (DP + split table)
dp[n][n] for costs and s[n][n] for optimal split points
Quadratic \(O(n^2)\)
🐌 Brute force
Number of parenthesizations grows as Catalan numbers — exponential in n
Catalan number count \(O(4^n / n^1.5)\)
🔍 Reconstruction
Follow split-point table recursively — at most n-1 splits
Linear \(O(n)\)

Quick check

Matrices A(2×3), B(3×4), C(4×2). Which parenthesization is cheaper?

Continue reading