Matrix Chain Multiplication

Interval DP · Optimal Parenthesization

1:00

How to find the optimal parenthesization of a matrix chain using interval dynamic programming, reducing exponential brute-force to O(n³).

By the end, you can

Compute the scalar-multiplication cost of multiplying two matrices given their dimensions.
Explain why associativity means the result is the same for all groupings but the cost can differ.
Describe why the Catalan-number growth of parenthesizations makes brute force impractical.
Explain why greedy (cheapest first) fails and why every split point must be tried.
State the optimal-substructure property that justifies the DP approach.
Trace the bottom-up DP: fill the base-case diagonal, then fill by chain length, then reconstruct from split points.
Read off any entry m[i][j] and s[i][j] from a worked DP table.
State the O(n³) time and O(n²) space complexity and explain where each factor comes from.
Name at least two real-world domains where interval DP is applied beyond matrix chains.

Up next in String Algorithms, Advanced DP & Competitive Techniques