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, Python, C++ and JavaScript, 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].

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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].
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.
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, Predict the Winner, The Score of Students Solving Math Expression.

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).