Matrix chain multiplication

Choose where to place the parentheses in a chain of matrix multiplications to minimise the total number of scalar multiplications.

The idea

Dimensions p describe n matrices, where matrix i is p[i-1] by p[i]. dp[i, j] is the cheapest cost of multiplying matrices i through j. Trying every split point k between i and j, the cost is the cost of the left group plus the right group plus one multiplication of the two resulting matrices together.

Code

public static int MatrixChainOrder(int[] p) {
    int n = p.Length - 1;
    var dp = new int[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;
            dp[i, j] = int.MaxValue;
            for (int k = i; k < j; k++) {
                int 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];
}

Tips

• A single matrix needs no multiplication, so every dp[i, i] is 0.
• The table is filled by increasing chain length, since a chain of length len always splits into two shorter, already-solved chains.

In the .NET library

Matrix multiplication is associative but not commutative, so only the grouping changes, never the order of the matrices. Picking a bad grouping on a long chain can cost orders of magnitude more multiplications than the best one.