Matrix Chain Multiplication

T.C. Hu & M.T. Shing, 1968

Formalized by T.C. Hu and M.T. Shing, matrix chain multiplication finds the parenthesization that minimizes the cost of multiplying a sequence of matrices. The DP table is upper-triangular, filled diagonal by diagonal: dp[i][j] stores the minimum cost of multiplying matrices i through j. The visualization fills cells in gold, marks completed cells in teal, and highlights the optimal split path in coral once the table is complete.