Matrix Chain Theory

1. Recurrence

dp[i][j] = min_{i<=k<j} dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]

2. Complexity

• O(n³) time iterating all lengths and splits.
• O(n²) space for dp + split table.

3. Reconstruction

Parenthesization built recursively: if split[i][j] = k then result = (solve(i,k))(solve(k+1,j)).

4. Tips & Patterns

• Typical interval DP loops: length from 2..n; start index i; j = i+length-1.
• Order ensures subintervals already computed when needed.
• Similar structure appears in polygon triangulation and optimal BST.