CONCEPT · International Grandmaster
Interval DP
also range DP · matrix chain
dp[l][r] on a contiguous segment. Grow by length, try splits. O(n²) states × O(n) = O(n³); n≤400 in C++.
Intuition
The last cut (or last balloon) splits the interval into two independent intervals you already solved.
When to reach for it
- Matrix chain, burst balloons, optimal BST
- CSES Removal Game (O(n²) — only ends), Rectangle Cutting
Usual pits
- Looping l,r without increasing length
- O(n³) at n=2000
- Bursting first instead of last when neighbors matter