Matrix Chain Multiplication

The problem, simply

You have a chain of matrices to multiply, like A x B x C x D. You may not change their order, but you may choose which pair to multiply first. That choice is where the brackets go: (AB)(CD) or ((AB)C)D or (A(BC))D and so on.

Multiplying a p x q matrix by a q x r matrix costs p * q * r small multiplications. The sizes come as one array d: matrix i is d[i - 1] x d[i]. Give back the smallest total cost.

A story to remember it

Picture it

Examples

Way 1: the simple way

Let cost(i, j) be the cheapest way to multiply matrices i to j.

1. If i == j, it is one matrix: 0.
2. Otherwise, try every split k from i to j - 1. The last multiplication joins i..k with k+1..j, and costs d[i - 1] * d[k] * d[j].
3. The answer is the smallest cost(i, k) + cost(k + 1, j) + d[i - 1] * d[k] * d[j].

class Solution {
    // matrices are numbered 1 to n, matrix i is d[i - 1] x d[i]
    public int cost(int[] d, int i, int j) {
        if (i == j) return 0;                         // one matrix is free
        int best = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {                 // the last join is after k
            int c = cost(d, i, k) + cost(d, k + 1, j) + d[i - 1] * d[k] * d[j];
            best = Math.min(best, c);
        }
        return best;
    }

    public int matrixChainOrder(int[] d) {
        return cost(d, 1, d.length - 1);
    }
}

How long it takes: a chain of n makes calls on every shorter left and right part, and the count of calls grows about three times for each extra matrix, O(3^n). Extra room: the call chain is at most n deep, O(n).

Way 2: the clever way

There are only about n^2 / 2 parts i..j. Keep each part's best cost in a table dp[i][j]. A part only needs shorter parts, so fill the table by chain length: first all pairs, then all triples, and so on.

1. dp[i][i] = 0 for every matrix.
2. For length 2 up to n, for every start i with j = i + len - 1:
3. Try every split k and keep the smallest dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j].
4. The answer is dp[1][n], the top right box.

In the table, dp[i][k] sits in the same row to the left, and dp[k + 1][j] sits in the same column below.

class Solution {
    public int matrixChainOrder(int[] d) {
        int n = d.length - 1;                       // number of matrices
        int[][] dp = new int[n + 1][n + 1];         // dp[i][i] = 0 already

        for (int len = 2; len <= n; len++) {        // short chains first
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {       // the last join is after k
                    int c = dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j];
                    if (c < dp[i][j]) dp[i][j] = c;
                }
            }
        }
        return dp[1][n];
    }
}

How long it takes: about n^2 / 2 boxes and up to n splits for each, O(n^3). Extra room: the table, O(n^2).

Watch out for

• Indexing: with n matrices the array d has n + 1 numbers. Matrix i is d[i - 1] x d[i].
• The join cost uses the outer sizes of the two parts, d[i - 1] * d[k] * d[j], not the sizes of single neighbors.
• Costs can overflow int for big sizes. Use long if sizes reach the thousands.
• Greedy (always multiply the cheapest pair first) is not safe. Try it on [40, 20, 30, 10, 30].

What interviewers ask next

• Print the brackets. Store the best k in split[i][j], then print recursively: ( + print(i, k) + print(k + 1, j) + ). For the example it gives ((A(BC))D).
• Why "the last join"? Every bracketing has exactly one last multiplication, and it splits the chain into a left part and a right part that are solved separately. That is the interval DP idea.
• Same pattern elsewhere: burst balloons, minimum cost to merge stones, optimal binary search tree, boolean parenthesization, minimum score triangulation of a polygon.
• Can it be faster? Hu and Shing found an O(n log n) method for this exact problem, but interviews expect O(n^3).

Remember this

Grown-up words: the train pieces are matrices, the stickers are scalar multiplications, choosing brackets is the parenthesization, the chart over (start, end) is interval dynamic programming, and the repeated parts are overlapping subproblems.