Matrix Chain Multiplication
dp[i][j] is the cheapest way to multiply Mi..Mj, trying every position for the last multiplication.
Decision · step 2 of 8Interval DP: Four matrices
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.
What you will see
The table fills by diagonal (interval length); each cell tries every split.
Cost
| Best | O(n^3) |
|---|---|
| Average | O(n^3) |
| Worst | O(n^3) |
| Space | O(n^2) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.