Reasoning over ranges
Interval DP solves problems on a segment by considering every way to split it. The state dp at i and j is the best answer for the subrange from i to j. Matrix chain multiplication, optimal triangulation, and burst balloons all fit this form.
The recurrence
For a range, try each split point k inside it:
- Combine the best for the left part i to k with the best for the right part k plus one to j.
- Add the cost of merging those two parts, which depends on the problem.
- Keep the best split.
Single element ranges are the base cases, often zero cost. The final answer is dp for the whole range.
Filling order
Process ranges by increasing length so that when you split a range, both halves are shorter and already solved. This length first ordering is the signature of interval DP.
Key idea
Interval DP computes the best answer for a range by trying every internal split into two already solved subranges and adding the merge cost, iterating ranges from short to long.