Page 34Dynamic Programming
34 — Matrix Chain Multiplication
Optimal parenthesization using interval DP.
Matrix Chain Multiplication
Cost recurrence
m[i][j] = min over k from i to j-1:
m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
s[i][j] stores the best split k for parenthesization.
Time: O(n³), Space: O(n²).