Most interval DP problems ask: what's the best way to process a range? The answer depends on where you split it. For range , you try every split point from i to j-1. Splitting at k means you process and separately, then combine. You pick the k that gives the best result. This creates choices per state, and states, giving time overall. Time complexity: .
Space complexity: for the dp table.
Space: for the DP table. That's the signature complexity of interval DP.