Given a chain of matrices A1, A2, A3,.....An, you have to figure out the most efficient way to multiply these matrices.

Question

Given a chain of matrices A1, A2, A3,.....An, you have to figure out the most efficient way to multiply these matrices i.e. determine where to place parentheses to minimise the number of multiplications.

You will be given an array p[] of size n + 1. Dimension of matrix Ai is p[i - 1]*p[i]. You need to find minimum number of multiplications needed to multiply the chain.

Input Format :

3
10 15 20 25
Output Format :

Line 1 : 8000

Answer 1

Sample Output Explanation :

There are two ways to multiply the chain - A1*(A2*A3) or (A1*A2)*A3.

If multiply in order A1*(A2*A3) then number of multiplications required are 15000.

If multiply in order (A1*A2)*A3 then number of multiplications required are 8000.

Thus minimum number of multiplications required are 8000

Answer 2

can you explain me how that chain can give that output?