Interval dynamic programming Created 2026-10-20 Updated 2026-11-05
Interval dynamic programming stores answers for contiguous index intervals and combines shorter intervals. It applies when an optimal object can be split at an internal index while keeping subproblems contiguous.
For matrix-chain multiplication, with matrix dimensions , define andThe final term is the scalar multiplication cost of combining the two products. Filling intervals in increasing length makes all dependencies available, giving time and storage. The recurrence optimizes parenthesization while retaining the original matrix order.