Matrix Chain Multiplication

Given the dimensions of a chain of matrices, where matrix i has size dims[i - 1] × dims[i], find the minimum number of scalar multiplications needed to compute their product. Matrix multiplication is associative, so the parentheses can go anywhere, but they change the cost a lot.

Example

Text

dims = [40, 20, 30, 10, 30]    (A: 40×20, B: 20×30, C: 30×10, D: 10×30)
Output: 26000   ((A(BC))D)

dims = [10, 20, 30]            (A: 10×20, B: 20×30)
Output: 6000    (10 · 20 · 30)

Multiplying a p × q matrix by a q × r matrix takes p · q · r multiplications and gives a p × r matrix. For dims = [10, 30, 5, 60], (AB)C costs 10·30·5 + 10·5·60 = 4,500, but A(BC) costs 30·5·60 + 10·30·60 = 27,000.

Brute force: try every split

The last multiplication of the chain i..j (inclusive) splits it into i..k and k+1..j for some k. Its cost is the cost of each half, plus dims[i-1] · dims[k] · dims[j] to multiply the two results.

Java

public class Main {
    static long cost(long[] dims, int i, int j) {
        if (i == j) return 0; // a single matrix
        long best = Long.MAX_VALUE;
        for (int k = i; k < j; k++) {
            long c = cost(dims, i, k) + cost(dims, k + 1, j) + dims[i - 1] * dims[k] * dims[j];
            best = Math.min(best, c);
        }
        return best;
    }

    static long matrixChain(long[] dims) {
        return cost(dims, 1, dims.length - 1);
    }

    public static void main(String[] args) {
        System.out.println(matrixChain(new long[]{40, 20, 30, 10, 30}) + " " + matrixChain(new long[]{10, 20, 30}) + " " + matrixChain(new long[]{10, 30, 5, 60}));
    }
}

Output

26000 6000 4500

Time: exponential (the number of ways to parenthesize grows like the Catalan numbers). Space: O(n) for the recursion.

Optimal: interval DP

The recursion only ever asks about contiguous chains i..j (inclusive), and there are O(n²) of them. Let m[i][j] be the cheapest cost for i..=j. A chain's cost depends only on shorter chains, so fill the table in order of chain length: all chains of 2 matrices, then 3, and so on.

Java

public class Main {
    static long matrixChain(long[] dims) {
        int n = dims.length - 1; // number of matrices, numbered 1..n
        long[][] m = new long[n + 1][n + 1];
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                long best = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    best = Math.min(best, m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j]);
                }
                m[i][j] = best;
            }
        }
        return m[1][n];
    }

    public static void main(String[] args) {
        System.out.println(matrixChain(new long[]{40, 20, 30, 10, 30}) + " " + matrixChain(new long[]{10, 20, 30}) + " " + matrixChain(new long[]{10, 30, 5, 60}));
        System.out.println(matrixChain(new long[]{10, 20, 30, 40, 30}) + " " + matrixChain(new long[]{5, 7}));
    }
}

Output

26000 6000 4500
30000 0

Time: O(n³): O(n²) chains, each trying up to n splits. Space: O(n²).

To print the parenthesization, also store the best k for each (i, j) and rebuild the expression recursively from (1, n).

Edge cases

One matrix: 0 multiplications.
Two matrices: only one way, dims[0] · dims[1] · dims[2].
Overflow: costs are products of three dimensions summed many times, so they're computed in long. int would overflow for dimensions around a thousand, and the overflow would wrap silently.