Given a chain of chain <M1, M2...Mn> of n two-dimensional matrices, write a program to fully parenthesize the product M1×M2×⋯×Mn in a way that minimizes the number of multiplications.
- Input: Array of integers M representing a chain of 2-D matrices such that the dimensions of the ith matrix is M[i-1] x M[i]. Find the most efficient way to multiply these matrices together.
- Output: Return the minimum number of multiplications needed to multiply the chain.
- The problem is not actually to perform the multiplications,
but merely to decide in which order to perform the multiplications.
- Assume that the matrix dimensions allow multiplication, in order
- Matrix multiplication is associative: M1 (M2M3) = (M1M2) M3
Input: M = [40, 20, 30, 10, 30] Output: 26000 Explanation: Dimensions of M1 = 40 x 20 Dimensions of M2 = 20 x 30 Dimensions of M3 = 30 x 10 Dimensions of M4 = 10 x 30 First, multiply M2 and M3,cost = 20*30*10 = 6000 Second, multilpy M1 and (Matrix obtained after multilying M2 and M3) = 40 * 20 * 10 = 8000 Third, multiply (Matrix obtained after multiplying M1, M2 and M3) and M4 = 40 * 10 * 30 = 12000 Total Cost = 12000 + 8000 + 6000 =26000
Input: A = [10, 20, 30] Output: 6000 Explanation: There are only two matrices of dimensions 10x20 and 20x30.So there is only one way to multiply the matrices, cost of which is 10*20*30.