Pattern - When Interval DP

Use interval DP when: the answer for a range depends on how you split it, and sub-ranges are independent after splitting. Common signals: "partition", "cut", "split", "merge adjacent", "remove from ends", "parenthesize".

The loop structure is always: iterate by length, then by start position, then by split point. Complexity is usually $O(n^3)$: $O(n^2)$ intervals times $O(n)$ split points. Some problems allow $O(n^2)$ with optimizations (Knuth's).