A tensor pipeline multiplies a chain of n matrices together, in the fixed left-to-right order M1 * M2 * ... * Mn. The dimensions are given by an array p of n+1 integers, where matrix Mi has p[i-1] rows and p[i] columns (1-indexed), so consecutive matrices are conformable.
Multiplying an a x b matrix by a b x c matrix takes a * b * c scalar multiplications and yields an a x c matrix. Matrix multiplication is associative, so you may fully parenthesize the chain however you like; different parenthesizations need different numbers of scalar multiplications. Report the minimum total number of scalar multiplications needed to compute the whole product.
Line 1: an integer n, the number of matrices.
Line 2: n+1 space-separated positive integers, the dimension array p.
A single integer: the minimum number of scalar multiplications (0 when n is 1).
Example 1
Input
3 10 20 30 40
Expected
18000
Explanation
Matrices are 10x20, 20x30, 30x40. Parenthesizing as (M1 M2) M3 costs 10*20*30 + 10*30*40 = 18000, beating M1 (M2 M3) which costs 32000.
Example 2
Input
1 5 7
Expected
0
Explanation
A single 5x7 matrix needs no multiplication, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →