Matrix Chain Multiplication

Matrix Chain Multiplication is the classic interval DP problem. You cannot change which matrices get multiplied, only the order you pair them up — and the right order can be hundreds of times cheaper than the wrong one.

The slow way first

Multiplying two matrices of shape a x b and b x c costs a · b · c scalar multiplications. For a chain, the order of pairings forms a binary tree, and the number of valid parenthesizations grows like the Catalan numbers — exponential. Trying them all is hopeless for anything but a tiny chain.

The question to ask: whatever the optimal order is, there must be one final multiplication that combines a left block and a right block. If I knew the best cost for every smaller block, I could just try each possible split point and take the cheapest. That is a textbook dynamic programming setup.

The idea: build up by chain length

Let dp[i][j] be the cheapest cost to multiply the sub-chain Ai … Aj. A single matrix needs no work, so dp[i][i] = 0. For a longer chain we try every place k to make the final cut:

dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j] )

The first two terms are the costs of the left and right blocks (already solved, because they are shorter); the third is the cost of the one multiplication that joins them. We fill the table in order of increasing chain length, so every subproblem a cell needs is already computed.

The cell being filled depends only on cells to its left (same row) and below (same column) — all of which belong to shorter chains, hence already done.

Walk through it

Step through the animation. The grid is dp[i][j] (row i, column j); only the upper triangle is used. The diagonal starts at 0. We fill length-2 chains, then length-3, then the full length-4 cell dp[1][4]. Watch the final cell try all three splits k = 1, 2, 3 and keep the cheapest, 26000.

Pseudocode

n = number of matrices
dp[i][i] = 0 for every i                 # one matrix costs nothing
for length = 2 to n:
    for i = 1 to n - length + 1:
        j = i + length - 1
        dp[i][j] = infinity
        for k = i to j - 1:              # try every split point
            cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
            if cost < dp[i][j]:
                dp[i][j] = cost          # keep the cheapest split
return dp[1][n]

The Python solution

def matrix_chain(p):
    n = len(p) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[1][n]

• n = len(p) - 1 is the number of matrices; p has one more entry than there are matrices.
• dp is (n+1) x (n+1), 1-indexed so dp[i][j] lines up with matrices Ai … Aj. The diagonal stays 0.
• We loop by length first so that when we compute dp[i][j], the shorter blocks it reads are filled.
• j = i + length - 1 is the right end of the current sub-chain.
• The inner k loop is the heart: every split point gives a candidate cost, and we keep the minimum.
• p[i - 1] * p[k] * p[j] is the cost of the single multiply that joins the left block Ai..Ak to the right block Ak+1..Aj.
• The answer for the whole chain is dp[1][n].

Complexity

There are O(n^2) subchains, and each scans up to n split points, giving O(n^3) time. The dp table holds the O(n^2) answers.

When this pattern shows up

Practice