Matrix Chain Multiplication

Practice this coding question on Coding Gurukul.

Problem statement

A graphics pipeline multiplies a fixed sequence of compatible matrices. Matrix multiplication is associative, so the pipeline may change the parenthesization while preserving matrix order to reduce the number of scalar multiplications. Your task Given n matrix dimensions as n+1 numbers d0 through dn, matrix i has shape d(i-1) by di. Find the minimum scalar multiplications needed to multiply all n matrices. Important details Multiplying an a-by-b matrix by a b-by-c matrix costs a*b*c. Do not reorder matrices. A chain of one matrix needs no multiplication. Intermediate dimensions depend on the entire chosen interval, not just the adjacent pair. Worked example Dimensions [10, 20, 30, 40] permit (AB)C at cost 6000 + 12000 = 18000. A(BC) costs 24000 + 8000 = 32000, so the minimum is 18000.

Input format

First line: n. Next line: n+1 dimensions.

Output format

Print the minimum multiplication count.

Constraints

1 <= n <= 100; 1 <= dimensions <= 500; use 64-bit arithmetic.

Sample input

3
10 20 30 40