Matrix Chain Multiplication: Interval DP Explained

Multiplying matrices is associative: (AB)C and A(BC) give exactly the same result. They do not cost the same. For a 10×30, a 30×5 and a 5×60 matrix, one order takes 4,500 scalar multiplications and the other 27,000. Matrix chain multiplication asks for the cheapest order, and it is the textbook introduction to interval DP, the family of dynamic programs indexed by a stretch i..j rather than a prefix. Once the shape clicks, burst balloons, palindrome partitioning and polygon triangulation are the same table with a different price.

The problem it solves

Multiplying a p×q matrix by a q×r matrix costs p·q·r scalar multiplications and yields a p×r matrix. A chain of n matrices is described by n + 1 dimensions: matrix i is dims[i] × dims[i+1].

For the lesson's chain, (AB)C first builds a 10×5 matrix for 1,500, then multiplies it by C for 3,000: 4,500. A(BC) builds a 30×60 matrix for 9,000, then multiplies A by it for 18,000: 27,000. Same product, six times the arithmetic.

Trying every order does not scale. The number of ways to parenthesise a chain is a Catalan number: 5 orders for four matrices, 429 for nine, and it grows roughly by a factor of four per extra matrix.

The intuition

Look at the last multiplication in any order. It joins a left part, matrices i..k, with a right part, k+1..j. Whatever happened inside each part, the final join costs dims[i] · dims[k+1] · dims[j+1], because the left part is a dims[i] × dims[k+1] matrix and the right part is dims[k+1] × dims[j+1].

So the cheapest way to multiply i..j is the cheapest over every cut k of: best cost of the left part, plus best cost of the right part, plus the join. That is the recurrence:

best[i][j] = min over k of best[i][k] + best[k+1][j] + dims[i]·dims[k+1]·dims[j+1], with best[i][i] = 0.

The parts are shorter stretches than i..j, so if the table is filled by length, pairs first, then triples, every value the recurrence reads is already known. That fill order is the signature of interval DP: not row by row, not left to right, but short stretches before long ones.

Nothing tells you where the best cut is, so every k is priced. Keeping the winning k for each cell in a second table lets you rebuild the order afterwards.

Watch it run

The animation labels the matrices A, B and C. A cell is a stretch of the chain, from matrix i to matrix j, and the diagonal is free: one matrix costs nothing to multiply. Then the stretches of length two. AB, cut after A: 0 + 0 + 10×30×5 = 1500. The cheapest cut for AB is after A, 1500, stored and never recomputed. BC, cut after B: 0 + 0 + 30×5×60 = 9000, stored. Then the whole chain, ABC, which has two cuts to price. Cut after A: 0 + 9000 + 10×30×60 = 27000. Cut after B: 1500 + 0 + 10×5×60 = 4500, which wins. The cheapest cut for ABC is after B, 4500. The closing frame compares the two: 4500 multiplications against 27000 for the other order, the same product with six times the arithmetic.

The code

The bottom-up table, filled by stretch length, with a second table remembering the winning cut so the order can be printed:

def matrix_chain(dims):
    """Matrix i is dims[i] x dims[i+1]. Returns (cost, split table)."""
    n = len(dims) - 1
    best = [[0] * n for _ in range(n)]
    split = [[None] * n for _ in range(n)]
    for length in range(2, n + 1):             # short stretches first
        for i in range(n - length + 1):
            j = i + length - 1
            best[i][j] = float("inf")
            for k in range(i, j):              # every place to cut i..j
                cost = best[i][k] + best[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                if cost < best[i][j]:
                    best[i][j], split[i][j] = cost, k
    return best[0][n - 1], split

def order(split, i, j, names):
    if i == j:
        return names[i]
    k = split[i][j]
    return "(" + order(split, i, k, names) + order(split, k + 1, j, names) + ")"

cost, split = matrix_chain([10, 30, 5, 60])
print(cost, order(split, 0, 2, "ABC"))     # 4500 ((AB)C)
print(10 * 30 * 60 + 30 * 5 * 60)          # 27000

cost, split = matrix_chain([40, 20, 30, 10, 30])
print(cost, order(split, 0, 3, "ABCD"))    # 26000 ((A(BC))D)

The same recurrence top-down, with memoisation doing the ordering for you. It is often the quicker version to write under pressure:

from functools import lru_cache

def matrix_chain_memo(dims):
    @lru_cache(maxsize=None)
    def cheapest(i, j):
        if i == j:
            return 0
        return min(cheapest(i, k) + cheapest(k + 1, j) + dims[i] * dims[k + 1] * dims[j + 1]
                   for k in range(i, j))
    return cheapest(0, len(dims) - 2)

print(matrix_chain_memo((40, 20, 30, 10, 30)))   # 26000

The brute force, which prices every possible parenthesisation. Counting what it enumerates for chains of one to eight matrices gives the Catalan numbers, which is why it is only good as a checker:

def brute_force(dims):
    def go(i, j):
        if i == j:
            return [0]
        costs = []
        for k in range(i, j):
            here = dims[i] * dims[k + 1] * dims[j + 1]
            costs += [a + b + here for a in go(i, k) for b in go(k + 1, j)]
        return costs
    return go(0, len(dims) - 2)

print([len(brute_force([1] * (n + 1))) for n in range(1, 9)])
# [1, 1, 2, 5, 14, 42, 132, 429]

def price(split, dims, i, j):
    """Follow the stored cuts and count the multiplications they really cause."""
    if i == j:
        return 0
    k = split[i][j]
    return price(split, dims, i, k) + price(split, dims, k + 1, j) + dims[i] * dims[k + 1] * dims[j + 1]

Checked on 400 seeded random chains of one to seven matrices: the table, the memoised version and the minimum over every parenthesisation must agree, and the rebuilt order must actually cost what the table claims:

import random

random.seed(25)
ok = True
for _ in range(400):
    dims = [random.randint(1, 30) for _ in range(random.randint(2, 8))]
    cost, split = matrix_chain(dims)
    ok &= cost == min(brute_force(dims)) == matrix_chain_memo(tuple(dims))
    ok &= price(split, dims, 0, len(dims) - 2) == cost
print(ok)                                  # True

The complexity

• Time: O(n³). There are about n²/2 stretches, and each tries up to n cuts. The Big-O cheat sheet lists it with the other DP classics.
• Space: O(n²) for the cost table, and the same again for the split table.
• Brute force: Catalan-many orders, exponential in n.

Where it goes wrong

• Filling row by row. best[i][j] needs best[k+1][j] from a later row; iterate by length, or memoise.
• Off-by-one in the dimensions. Matrix i is dims[i] × dims[i+1], so the join is dims[i] · dims[k+1] · dims[j+1], not dims[k].
• Initialising to zero. A cell that takes a min must start at infinity, or no cut ever beats it.
• Greedy cuts. A fixed rule, such as cutting at the largest dimension, fails on some inputs; only pricing every cut is safe.
• Forgetting to store the cut. Without the split table, you know the cost but cannot say the order.

When it shows up in interviews

The chain itself is asked less often than its relatives, which share the same skeleton: burst balloons, where the last balloon to burst in a stretch plays the cut; minimum cost to cut a stick; palindrome partitioning; minimum score triangulation of a polygon. Recognising "the answer for a stretch depends on every way to split it" is the skill being tested. The table-order question, and why memoisation sidesteps it, is covered in memoization vs tabulation.

How to say it in an interview

"The state is a stretch of matrices i..j. Any order has a last multiplication that joins i..k with k+1..j, costing dims[i]·dims[k+1]·dims[j+1] on top of the two parts, so the best cost is the minimum of that over every k. Single matrices cost zero. The parts are shorter stretches, so I fill by length, or memoise. That is O(n²) states times O(n) cuts, O(n³) time and O(n²) space, against Catalan-many orders for brute force. I keep the winning k per cell to rebuild the parenthesisation."