Solve the Matrix Chain Multiplication problem.

Minimize scalar multiplications for multiplying chain of matrices A1*A2*...*An. Different parenthesizations yield different costs. DP solution: dp[i][j] = minimum cost to multiply matrices i to j. For each possible split point k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]). Solve for increasing chain lengths. Time O(n^3), space O(n^2). Classic example of DP with optimal substructure.