Matrix Chain Multiplication

Difficulty: 1900 6000 ms 128 MB

dp interval-dp

You must multiply a chain of matrices whose dimensions are d₀×d₁, d₁×d₂, ..., d_N−1×d_N. Multiplying a p×q by a q×r matrix costs p·q·r scalar multiplications. Print the minimum total cost over all parenthesizations.

Input: the first line has N (the number of matrices); the second line has the N+1 dimensions d₀..d_N.

Output: the minimum multiplication cost.

Constraints:

• 1 ≤ N ≤ 500
• 1 ≤ d_i ≤ 100

Sample Tests

3
10 20 5 15

1750

1
3 4

0

Read the Editorial