Matrix chain multiplication
HardTry every split point
Problem
Given matrix dimensions, find the minimum scalar multiplications to multiply the chain.
Interval DP: try every split point for the last multiplication and keep the cheapest.
The idea
For each interval of matrices, try every place to break it in two, costing the two halves plus the multiplication joining them. Filling by increasing interval length ensures both halves are already solved.
The trick
- Cost of a split at k: dp[i][k] + dp[k+1][j] + dims[i-1]·dims[k]·dims[j].
- Fill by interval length, not by index.
- O(n³) — the archetypal interval DP.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — dims=[10,20,30,40] Values: 10, 20, 30, 40.
1dp[i][j]=min over k of dp[i][k]+dp[k+1][j]+cost(i,k,j)Input
- array
- [10, 20, 30, 40]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- dims = [10,20,30,40,30]
- Output:
- 30000
- Explanation:
- Best parenthesisation needs 30000 multiplications.
Example 2
- Input:
- dims = [10,20,30]
- Output:
- 6000
- Explanation:
- One product → 6000.
Example 3
- Input:
- dims = [40,20,30,10,30]
- Output:
- 26000
- Explanation:
- Optimal order → 26000.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.