When to Use Interval DP

These signs usually signal interval DP:

$1.$ Operations on ranges. Merging, splitting, or removing contiguous elements.

$2.$ Subproblem independence. Solving $[l, k]$ and $[k+1, r]$ doesn't affect each other.

$3.$ Polynomial complexity hint. Constraints like $n \le 500$ suggest $O(n^3)$ is acceptable.

The state is typically $dp[l][r]$ representing the answer for range $[l, r]$.