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 and
The 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.

Articles by others on the same topic (0)

There are currently no matching articles.