AlgoScope

Matrix Chain Multiplication

dp[i][j] is the cheapest way to multiply Mi..Mj, trying every position for the last multiplication.

Dynamic programming, algorithm, advanced
dp 0 1 is 6000.0123012306000000
dp 0 1 is 6000.0123012306000000

Interval DP: Four matrices

Decision, step 2 of 8

dp[0][1], length 2: split at 0: 0 + 0 + 6000 = 6000. Best is 6000, splitting at 0: multiply (M0..M0), a 10 x 20, by (M1..M1), a 20 x 30, for 10 x 20 x 30 = 6000.

Cost

Best
O(n^3)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)

Taught by the same lesson

Interval DP covers these too, in the same run.