Description
Given an array p where matrix Ai has dimension p[i-1] x p[i], find the minimum number of scalar multiplications needed to multiply the chain.
Examples
Input:
p = [40, 20, 30, 10, 30]Output:
26000Explanation:
Optimal parenthesization minimizes multiplications.
Input:
p = [1, 2, 3, 4, 5]Output:
38Explanation:
Four matrices: A1(1x2), A2(2x3), A3(3x4), A4(4x5). The optimal parenthesization is ((A1*A2)*(A3*A4)). Cost: A1*A2=1*2*3=6, A3*A4=3*4*5=60, then (A1*A2)*(A3*A4)=1*3*5=15. Total: 6+60+15=81.
Input:
p = [5, 4, 6, 2, 7]Output:
158Explanation:
Four matrices: A1(5x4), A2(4x6), A3(6x2), A4(2x7). The optimal parenthesization is (A1*(A2*A3))*A4. First A2*A3=4*6*2=48, then A1*(A2*A3)=5*4*2=40, finally the result times A4=5*2*7=70. Total: 48+40+70=158.
Constraints
- •
1 ≤ p.length ≤ 100 - •
1 ≤ p[i] ≤ 500