Matrix Chain Multiplication: interval DP for minimum multiplications

• Matrix chain multiplication – finding the optimal way to parenthesise a chain of matrices to minimise scalar multiplications.
• Interval DP – a dynamic programming pattern where the state is a contiguous range and the transition tries every split point.
• Dimension array – array p where matrix i has dimensions p[i-1] by p[i].
• Recurrence – dp[i][j] = min over k in [i, j) of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j].
• Base case – dp[i][i] = 0 because a single matrix needs no multiplication.
• Complexity – O(n^3) time and O(n^2) space.

What is matrix chain multiplication?

Matrix chain multiplication is the problem of finding the most efficient way to multiply a sequence of matrices. Matrix multiplication is associative, so the final product is the same no matter how you parenthesise the chain. But the number of scalar multiplications depends heavily on the grouping.

If matrix A is 10x30 and matrix B is 30x5, multiplying them costs 10 * 30 * 5 = 1500 scalar multiplications and produces a 10x5 matrix. If matrix C is 5x60, multiplying (AB)C costs 1500 + 10 * 5 * 60 = 4500 total, while multiplying A(BC) costs 30 * 5 * 60 + 10 * 30 * 60 = 27000 total. The parenthesisation changes the cost by a factor of six.

package com.bank.dsa;

public class MatrixChainBasic {

    public static int minMultiplications(int[] p) {
        int n = p.length - 1;  // number of matrices
        int[][] dp = new int[n][n];

        // chain length 1: single matrix, cost = 0 (already in dp as default)
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] dimensions = {10, 30, 5, 60};
        System.out.println("Min multiplications: " + minMultiplications(dimensions));
    }
}

Min multiplications: 4500

Why does the grouping order matter?

Multiplying an (a x b) matrix by a (b x c) matrix costs a * b * c scalar multiplications and produces an (a x c) matrix. In a chain of matrices with very different dimensions, an unlucky grouping can force large intermediate matrices and enormous costs, while a good grouping keeps the intermediates small.

The number of possible parenthesisations grows as the Catalan numbers, which are exponential. For 10 matrices there are 4862 groupings. For 20 matrices there are over 1.7 billion. Trying all of them is infeasible, which is why dynamic programming is needed.

How does the interval DP recurrence work?

The dimensions are stored in an array p of size n + 1, where matrix i has dimensions p[i] by p[i + 1] (using 0-based indexing for the matrices). We define dp[i][j] as the minimum cost to multiply the subchain from matrix i to matrix j.

A single matrix (i == j) needs no multiplication, so dp[i][i] = 0. For a longer chain, we try every split point k between i and j. Splitting at k means we first multiply the left subchain (i to k) and the right subchain (k + 1 to j), and then multiply the two resulting matrices together. The cost of that final multiplication is p[i] * p[k + 1] * p[j + 1].

package com.bank.dsa;

public class MatrixChainDetailed {

    public static int solve(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n][n];
        int[][] split = new int[n][n];  // stores optimal split point

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        }
        System.out.println("Optimal parenthesization: " + buildParens(split, 0, n - 1));
        return dp[0][n - 1];
    }

    private static String buildParens(int[][] split, int i, int j) {
        if (i == j) return "M" + (i + 1);
        return "(" + buildParens(split, i, split[i][j])
             + " x " + buildParens(split, split[i][j] + 1, j) + ")";
    }

    public static void main(String[] args) {
        int[] p = {40, 20, 30, 10, 30};
        System.out.println("Min cost: " + solve(p));
    }
}

Optimal parenthesization: ((M1 x (M2 x M3)) x M4)
Min cost: 26000

How do you fill the table by chain length?

The table is filled diagonally by increasing chain length. Chain length 1 has cost zero (the diagonal). Chain length 2 fills the entries one above the diagonal. Chain length 3 fills the next diagonal, and so on until the full chain.

This order guarantees that when we compute dp[i][j], all shorter subchains dp[i][k] and dp[k+1][j] are already computed.

How is this different from the recursive top-down approach?

| Aspect | Bottom-up tabulation | Top-down memoization |
|---|---|---|
| Fill order | By increasing chain length | Recursion fills on demand |
| Base case | dp[i][i] = 0 on the diagonal | Return 0 when i == j |
| Space | O(n^2) table | O(n^2) memo + recursion stack |
| Stack overflow | No risk | Risk for very long chains |
| Code style | Three nested loops | Recursive with memo check |

package com.bank.dsa;

import java.util.Arrays;

public class MatrixChainMemo {

    private static int[][] memo;
    private static int[] p;

    public static int solve(int[] dimensions) {
        p = dimensions;
        int n = p.length - 1;
        memo = new int[n][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dp(0, n - 1);
    }

    private static int dp(int i, int j) {
        if (i == j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int best = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
            best = Math.min(best, dp(i, k) + dp(k + 1, j) + p[i] * p[k + 1] * p[j + 1]);
        }
        return memo[i][j] = best;
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[]{10, 30, 5, 60}));
    }
}

4500

What are common mistakes?

The most common mistake is getting the dimension indices wrong. With 0-based matrix indexing, matrix i has dimensions p[i] by p[i + 1], and the cost of combining the left and right subchains after splitting at k is p[i] * p[k + 1] * p[j + 1]. Mixing up these indices produces wrong answers silently.

// WRONG: using p[i-1] * p[k] * p[j] with 0-based matrix indexing
int cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];  // off by one if matrices are 0-indexed

// CORRECT: with 0-based matrix indexing
int cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1];

Another mistake is initialising dp[i][j] to zero instead of Integer.MAX_VALUE before the inner loop, which would make the minimum always zero.

What are the edge cases?

With one matrix, the answer is zero. With two matrices, the answer is simply p[0] * p[1] * p[2] with no choice to make. The interesting cases start at three matrices.

package com.bank.dsa;

public class MatrixChainEdgeCases {
    public static void main(String[] args) {
        System.out.println(MatrixChainBasic.minMultiplications(new int[]{10, 20}));        // 0
        System.out.println(MatrixChainBasic.minMultiplications(new int[]{10, 20, 30}));    // 6000
        System.out.println(MatrixChainBasic.minMultiplications(new int[]{10, 30, 5, 60})); // 4500
    }
}

0
6000
4500

When should you use interval DP in banking?

At the National Bank of India, the risk computation engine multiplies a chain of covariance and factor matrices for portfolio risk. The dimensions vary widely because some matrices represent individual securities and others represent market factors. The engine runs the matrix chain DP to find the cheapest multiplication order before executing the actual matrix operations, saving orders of magnitude in floating-point work on large portfolios.

package com.bank.service;

public class RiskMatrixOptimiser {

    public static int optimiseChain(int[] factorDimensions) {
        int n = factorDimensions.length - 1;
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++)
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j],
                        dp[i][k] + dp[k+1][j]
                        + factorDimensions[i] * factorDimensions[k+1] * factorDimensions[j+1]);
            }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] dims = {100, 20, 50, 10, 80};
        System.out.println("Minimum scalar multiplications: " + optimiseChain(dims));
    }
}

Minimum scalar multiplications: 220000

What should a senior engineer know?

A senior engineer should know that matrix chain multiplication is the archetypal interval DP problem. The pattern of choosing a split point within a range and combining the costs of the two halves appears in burst balloons, minimum cost to cut a stick, and optimal binary search tree.

The number of parenthesisations follows the Catalan numbers, C(n) = (2n)! / ((n+1)! * n!), which grows exponentially. The cubic DP is a massive improvement over exhaustive enumeration.

Knuth's optimisation can sometimes reduce the cubic time by constraining the range of k values, but the standard O(n^3) version is what interviewers expect.