Ranges as states
Interval dynamic programming solves problems where the answer for a contiguous range depends on answers for smaller ranges inside it. The state is a pair: the left and right ends of a segment. You fill the table for short segments first, then progressively longer ones.
The split point
The core move is to pick a split or a special element within the range. For matrix chain multiplication you choose where to place the outermost parenthesis. For optimal triangulation you choose a vertex to anchor a triangle. For bursting balloons you choose which balloon to pop last.
- Fix the range from left to right.
- Try every split point inside it.
- Combine the answer for the left part, the answer for the right part, and the cost of the split.
- Keep the best combination.
Why order matters
Longer ranges depend on shorter ones, so you must compute by increasing length. A common loop iterates over lengths, then over left endpoints, then over split points. This gives a cubic amount of work in the range size, acceptable for moderate inputs.
Key idea
Let the state be a range and choose the best internal split, computing in order of increasing length so every smaller range is ready when you need it.