Matrix Chain Multiplication
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
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];}