The Split Point Approach

Most interval DP problems ask: what's the best way to process a range? The answer depends on where you split it. For range $[i,j]$, you try every split point $k$ from i to j-1. Splitting at k means you process $[i,k]$ and $[k+1,j]$ separately, then combine. You pick the k that gives the best result. This creates $O(n)$ choices per state, and $O(n^2)$ states, giving $O(n^3)$ time overall. Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$ for the dp table.

Space: $O(n^2)$ for the DP table. That's the signature complexity of interval DP.