hard

Matrix Chain Multiplication

You must multiply a chain of n matrices where matrix i has dimensions p[i-1] × p[i]. The product is fixed but the parenthesization is free. Return the minimum number of scalar multiplications needed.

Constraints

2 ≤ p.length ≤ 500
1 ≤ p[i] ≤ 1000

Examples

in: p = [10, 20, 30, 40, 30]

out: 30000

((A·B)·C)·D.

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.