Loading...
Loading...
Loading...
A chain of N matrices is multiplied in one line. Matrix i has D[i] rows and D[i + 1] columns. Multiplying a p by q matrix with a q by r matrix costs p x q x r steps. The order of the brackets changes the total cost. Print the smallest total cost for the whole chain.
Example
Input
10 30 5 60
Output
4500
Three matrices. Joining the first two before the last costs 4500.
Try the problem first. Open one hint at a time.
Let cost[i][j] be the cheapest way to multiply matrices i to j. A single matrix costs 0.
Try every split point k and add the two parts plus D[i] x D[k + 1] x D[j + 1]. Fill by increasing length.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor