Skills101
← All coding problems

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 + 1 dimensions p[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).

Loading editor…

Log in to run and submit your code — it's free.