Matrix Chain Multiplication
mediumDynamic Programming II+20 XPTime limit 3s
You must multiply n matrices A₁ · A₂ · … · Aₙ, where Aᵢ has size p[i−1] × p[i]. Multiplying an x × y matrix by a y × z matrix costs x · y · z scalar multiplications. The product is the same whatever brackets you use, but the cost is not. Find the minimum total cost.
Input:
- line 1:
n - line 2:
n + 1dimensionsp[0] … p[n]
Output: the minimum number of scalar multiplications (0 when n = 1).
Constraints: 1 ≤ n ≤ 200, 1 ≤ p[i] ≤ 100.
Example: sizes 10×30, 30×5, 5×60: (A₁A₂)A₃ costs 1500 + 3000 = 4500, but A₁(A₂A₃) costs 27000. Answer: 4500.
Think about it: interval DP. cost[i][j] = cheapest way to multiply Aᵢ … Aⱼ; try every last split point k: cost[i][k] + cost[k+1][j] + p[i−1]·p[k]·p[j]. Fill by increasing interval length. O(n³).
Sample input 1
3 10 30 5 60
Sample output 1
4500
Sample input 2
1 5 7
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).