Start practising

Matrix Chain Multiplication

Hard Dynamic Programming Interval DP Original on GeeksforGeeks

Matrix Chain Multiplication is a hard dynamic programming problem solved with the interval dp pattern. The best approach, optimal (interval dp by chain length), runs in O(n³) time and O(n²) space. Below are 2 approaches in Java, from recursion over split points up.

Problem

A chain of matrices has dimensions given by arr: matrix i is arr[i - 1] × arr[i]. Multiplying a p × q matrix by a q × r matrix costs p · q · r. Choose where to put the brackets so that multiplying the whole chain has the minimum total cost.

Examples

Example 1

Input
arr = [2, 1, 3, 4]
Output
20
Why
Matrices 2×1, 1×3, 3×4. (A·B)·C costs 6 + 24 = 30; A·(B·C) costs 12 + 8 = 20.

Example 2

Input
arr = [1, 2, 3, 4, 3]
Output
30

Constraints

  • 2 <= arr.length <= 100; matrix i has size arr[i - 1] × arr[i].

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Recursion over split pointsexponentialO(n)
Optimal (interval DP by chain length)O(n³)O(n²)

1Recursion over split points

Timeexponential
SpaceO(n)

Try every split k between i and j and take the cheapest.

  1. f(i, i) = 0.
  2. f(i, j) = min over k of f(i, k) + f(k + 1, j) + arr[i - 1] * arr[k] * arr[j].
Java
class Solution {
    static int matrixMultiplication(int[] arr) {
        return f(arr, 1, arr.length - 1);
    }

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

2Optimal (interval DP by chain length)

TimeO(n³)
SpaceO(n²)

dp[i][j] = cheapest cost for matrices i..j. Fill by increasing length so both halves of every split are already computed.

  1. For len = 2..n - 1, for i, j = i + len - 1: dp[i][j] = min over k.
Java
class Solution {
    static int matrixMultiplication(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int len = 2; len < n; len++)
            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++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]);
            }
        return dp[1][n - 1];
    }
}

Edge cases to test

  • Only one matrix (cost 0)

Hints

Hint 1

Pick the last multiplication k splitting matrices i..j into i..k and k + 1..j. Cost = left + right + arr[i - 1] · arr[k] · arr[j].

FAQ

What is the best time complexity for Matrix Chain Multiplication?

Optimal (interval DP by chain length) runs in O(n³) time and O(n²) extra space.

Which pattern does Matrix Chain Multiplication use?

It is a dynamic programming problem that uses the interval dp pattern. Other problems with the same pattern: Burst Balloons.

Is there a brute force solution for Matrix Chain Multiplication?

Yes. Recursion over split points takes exponential time and O(n) space. Try every split k between i and j and take the cheapest.

Which edge cases should I test for Matrix Chain Multiplication?

Only one matrix (cost 0).