Matrix Chain Multiplication

Hard

Problem

Matrix i has dimensions p[i−1] × p[i]. Choose where to put the parentheses in the product so that the total number of scalar multiplications is as small as possible. Return that minimum.

Example 1

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

(A(BC))D.

Also asked as: Matrix Chain Multiplication

Test cases

Case 1

Input:    [40,20,30,10,30]
Expected: 26000

Case 2

Input:    [10,20,30,40,30]
Expected: 30000

Case 3

Input:    [10,20,30]
Expected: 6000

Case 4

Input:    [5,10]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Interval DP over split points

Time O(n³)Space O(n²)

dp[i][j] = min scalar multiplications to multiply matrices i..j. Try every split k: dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j].

function matrixChainOrder(p) { // p has length n+1 for n matrices
const n = p.length - 1;
const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).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++) {
const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j]) dp[i][j] = cost;
}
}
}
return dp[1][n];
}