Matrix Chain Multiplication
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Recursion over split points | exponential | O(n) |
| Optimal (interval DP by chain length) | O(n³) | O(n²) |
1Recursion over split points
exponentialO(n)Try every split k between i and j and take the cheapest.
- f(i, i) = 0.
- 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;
}
}class Solution:
def matrixMultiplication(self, arr: List[int]) -> int:
return self.f(arr, 1, len(arr) - 1)
def f(self, a: List[int], i: int, j: int) -> int:
if i == j:
return 0
best = math.inf
for k in range(i, j):
best = min(best, self.f(a, i, k) + self.f(a, k + 1, j) + a[i - 1] * a[k] * a[j])
return bestclass Solution {
public:
int matrixMultiplication(vector<int>& arr) {
return f(arr, 1, (int) arr.size() - 1);
}
private:
int f(vector<int>& a, int i, int j) {
if (i == j) return 0;
int best = INT_MAX;
for (int k = i; k < j; k++)
best = min(best, f(a, i, k) + f(a, k + 1, j) + a[i - 1] * a[k] * a[j]);
return best;
}
};function matrixMultiplication(arr) {
return f(arr, 1, arr.length - 1);
}
function f(a, i, j) {
if (i === j) return 0;
let best = Infinity;
for (let 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)
O(n³)O(n²)dp[i][j] = cheapest cost for matrices i..j. Fill by increasing length so both halves of every split are already computed.
- 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];
}
}class Solution:
def matrixMultiplication(self, arr: List[int]) -> int:
n = len(arr)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for i in range(1, n - length + 1):
j = i + length - 1
dp[i][j] = math.inf
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j])
return dp[1][n - 1]class Solution {
public:
int matrixMultiplication(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len < n; len++)
for (int i = 1; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]);
}
return dp[1][n - 1];
}
};function matrixMultiplication(arr) {
const n = arr.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let len = 2; len < n; len++)
for (let i = 1; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let 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).