Skip to main content
Back to ChallengesMatrix Chain MultiplicationHard 35 min

Matrix Chain Multiplication

Given a sequence of matrices, find the most efficient way to multiply these matrices together. Decide the ordering to minimize the count of scalar multiplications. Input is an array p where p[i-1] x p[i] represents dimensions of Ai.

Examples

Input: p = [40, 20, 30, 10, 30]
Output: 26000
Min multiplications cost is (A1 * (A2 * A3)) * A4 or similar configuration, cost 26000.

Constraints

  • • 2 <= p.length <= 100
  • • 1 <= p[i] <= 500

Complexity Analysis

Time
O(n^3)
where n is the number of matrices.
Space
O(n^2)
2D table representing optimal subsegment splits.

Test Cases

#1 4 matrices
Input: [40, 20, 30, 10, 30]
Expected: 26000
#2 2 matrices
Input: [10, 20, 30]
Expected: 6000
JavaScript
Output
Click "Run Code" to see output here...