Core Concept

Interval DP (dynamic programming) solves problems where you need to find the optimal way to process a contiguous range. In interval DP, $dp[i][j]$ represents the answer for elements from index i to j.

The key difference from other DP: instead of building from smaller indices, you build from shorter ranges to longer ones. A range of length $1$ is your base case. Then length $2$, then $3$, and so on. Why ranges? Some problems have this structure: the answer for $[i,j]$ depends on how you split it into $[i,k]$ and $[k+1,j]$. You try all split points $k$ and pick the best.