Matrix Chain Multiplication
Mastery
Matrix i has dims[i] rows and dims[i + 1] columns, so len(dims) - 1 matrices are given. Multiplying a p x q matrix by a q x r matrix costs p * q * r scalar multiplications. The order of the multiplications (the brackets) changes the total cost. Return the smallest total cost to multiply the whole chain. With fewer than two matrices the cost is 0.
For dims = [10, 30, 5, 60] the answer is 4500 ((A B) C).
Examples
Example 1
Input:
matrix_chain_cost([10, 30, 5, 60])
Output:
4500
Example 2
Input:
matrix_chain_cost([40, 20, 30, 10, 30])
Output:
26000
Constraints
0 <= len(dims) <= 1211 <= dims[i] <= 100
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.