246. Matrix Chain Multiplication
HardInterval DP
Matrices A₁…Aₙ have dimensions p₀×p₁, p₁×p₂, …. Print the minimum number of scalar multiplications to compute their product.
Input format
Line 1: n + 1 Line 2: p₀ … pₙ
Output format
The minimum cost.
Example 1
Input
5 40 20 30 10 30
Output
26000
Example 2
Input
3 10 20 30
Output
6000
Constraints
2 ≤ n + 1 ≤ 200
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…