Interval DP solves problems where you make decisions about ranges and combine solutions from smaller ranges. Classic examples include palindrome partitioning, optimal game strategies, and string encoding.
The pattern appears when your problem has optimal substructure over contiguous segments. You split the range at some point , solve and independently, then combine. The answer for the full array is . I will explain this in more detail through the examples.
