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.