Given a 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 arr[] representing a chain of 2-D matrices such that the dimensions of the i -th matrix is arr[i-1] x arr[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: arr[] = [10, 20, 30, 40, 30]
Output: 30000
Explanation:
Dimensions of M1 = 10 x 20
Dimensions of M2 = 20 x 30
Dimensions of M3 = 30 x 40
Dimensions of M4 = 40 x 30
First, multiply M1 and M2,cost = 10*20*30 = 6000
Second, multilpy (Matrix obtained after multilying M1 and M2) and M3 =  10 * 30 * 40 = 12000
Third, multiply (Matrix obtained after multiplying M1, M2 and M3) and M4 =  10 * 40 * 30 = 12000
Total Cost = 6000 + 12000 + 12000 = 30000

Example 2 

Input: arr[] = [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.