Interval DP and Matrix Chain Multiplication

Multiplying matrices $A$, $B$, and $C$ gives the same result whichever order you group the multiplications in — $(AB)C$ equals $A(BC)$ — but the number of arithmetic operations needed can differ enormously depending on the grouping, because each individual matrix multiply's cost depends on the dimensions involved. The matrix chain problem asks: given a sequence of matrices with known dimensions, which parenthesization minimizes total work?

Interval DP solves this by computing the best cost for every contiguous sub-chain, smallest first. Define $\text{cost}[i][j]$ as the cheapest way to multiply matrices $i$ through $j$. For a chain of length 1 there's no multiplication needed, so cost is zero; for longer chains, try every possible split point $k$ between $i$ and $j$, add the cost of the left part, the right part, and the cost of combining those two results, and keep the cheapest split. Because $\text{cost}[i][j]$ only depends on sub-intervals strictly shorter than $[i,j]$, filling the table by increasing interval length guarantees every value needed is already computed.

The same "try every split point over increasing interval lengths" pattern recurs throughout interview-style DP problems — optimal binary search trees, palindrome partitioning, and burst-balloon-style problems all reduce to the identical loop structure over intervals rather than matrices specifically.