Matrix Chain Multiplication

Hard25–30 min

Topics

Dynamic ProgrammingInterval DP

Companies

AmazonMicrosoftGoogle

A chain of matrices needs to be multiplied together in order — matrix 1 by matrix 2 by matrix 3 and so on — but matrix multiplication only cares about doing the pairs in the right order, not which pair gets combined first. Because it's associative, `(A1 A2) A3` and `A1 (A2 A3)` produce the identical final matrix, yet the number of individual number-multiplications spent getting there can differ enormously depending on the sizes involved. Given the dimensions of each matrix in the chain (as an array `p` where matrix i is p[i-1]×p[i]), find the cheapest possible parenthesization. The key structural fact: whatever the best full parenthesization turns out to be, it has some *last* multiplication — a single split point where everything to its left became one matrix and everything to its right became another. That means the best way to combine matrices i through j is entirely determined by the best way to combine i through some k, the best way to combine k+1 through j, and the cost of that one final multiply — for whichever k turns out cheapest. Solving every sub-chain from the shortest upward, and reusing each answer rather than re-deriving it, turns an exponential search into a cubic one.

Test Case 1:

Input:p = [1,2,3,4]

Output:18

Explanation:Three matrices sized 1×2, 2×3, and 3×4. Grouping the first pair together — (A1A2)A3 — costs 1×2×3 + 1×3×4 = 6 + 12 = 18, which beats grouping the last pair first (2×3×4 + 1×2×4 = 32).

Test Case 2:

Input:p = [40,20,30,10,30]

Output:26000

Explanation:Four matrices where the naive left-to-right grouping is far from optimal — trying every split point finds a much cheaper parenthesization.

Test Case 3:

Input:p = [1,1]

Output:0

Explanation:Only one matrix in the chain (1×1 → 1×1) — there's nothing to multiply together, so the cost is 0.

Constraints

◆2 ≤ p.length ≤ 8 (a chain of p.length - 1 matrices)
◆1 ≤ p[i] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

For a chain of matrices from position i to j, the last multiplication performed is always some split point k: everything from i to k becomes one matrix, everything from k+1 to j becomes another, and those two get multiplied together at the end. Trying every possible k and taking the cheapest one is correct, but two different splits can ask for the cost of the exact same sub-chain — e.g. matrices 2 through 4 might get re-solved once as part of a split at k=1 and again as part of a split at k=3 — and without remembering the answer, each of those re-derives it from scratch.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    public int matrixChainOrder(int[] p) {
        int n = p.length - 1;
        if (n <= 1) return 0;
        return solve(1, n, p);
    }

    private int solve(int i, int j, int[] p) {
        if (i == j) return 0;
        int min = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
            int cost = solve(i, k, p) + solve(k + 1, j, p) + p[i - 1] * p[k] * p[j];
            if (cost < min) min = cost;
        }
        return min;
    }
}

Optimal — Bottom-Up Interval DP

Optimal

Build the answer for every sub-chain from the shortest up to the full chain. dp[i][j] holds the minimum cost to multiply matrices i through j. A chain of length 1 (a single matrix) always costs 0. For longer chains, try every split point k between i and j: the cost is dp[i][k] (already known — it's shorter) plus dp[k+1][j] (also already known) plus the cost of multiplying the two resulting matrices together, p[i-1]×p[k]×p[j]. Filling shorter chains first guarantees every dp[i][k] and dp[k+1][j] a longer chain depends on is already sitting there ready to use.

TimeO(n³)

SpaceO(n²)