Interval dynamic programming
ID: interval-dynamic-programming
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.
New to topics? Read the docs here!