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.

Problem Note

• 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

Example 1

``````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``````

`Example 2`

``````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.``````