Matrix Chain Multiplication
HardP3Coding
You must multiply a chain of n matrices A1 * A2 * ... * An, where matrix Ai has dims[i - 1] rows and dims[i] columns (so dims has n + 1 entries). Multiplying a p x q matrix by a q x r matrix takes p * q * r scalar multiplications. Matrix multiplication is associative, so you may choose the order (the parenthesisation).
Return the minimum total number of scalar multiplications. With a single matrix, the answer is 0.
Example 1
- Input
- dims = [10,30,5,60]
- Output
- 4500
- Why
- Multiply the first two (10*30*5 = 1500) then by the third (10*5*60 = 3000): 4500.
Example 2
- Input
- dims = [40,20,30,10,30]
- Output
- 26000
Example 3
- Input
- dims = [10,20,30]
- Output
- 6000
Constraints
- 2 <= dims.length <= 101
- 1 <= dims[i] <= 100
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.