Matrix Chain Multiplication — Filling the Interval DP Table

dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j] ). Watch the table fill by increasing chain length, the split point k that wins, and the reconstructed parenthesization.

step 0

dp table (cost) — chain length L = -

Press Step to begin filling the table by increasing chain length.
left sub-chain dp[i][k] right sub-chain dp[k+1][j] current dp[i][j]

split table & reconstruction

—
We fill dp diagonal by diagonal: length-1 intervals cost 0, then length 2, 3, … up to the whole chain. Each cell tries every split k and keeps the minimum.
Self-contained visualization. Matrices are 1-indexed: matrix Aᵢ has shape p[i-1] × p[j]; multiplying p×q by q×r costs p·q·r. The diagonal dp[i][i] = 0. The split table records the winning k for reconstruction. See junior.md and professional.md for the optimal-substructure proof.