Algorithms / Interval Dp
Least You Need to Know: Interval DP, Length Order, and Split-Point Recurrences
Interval DP appears when the answer for a segment depends on smaller subsegments inside it. The recurring choices are the interval state, the base case for tiny segments, and the split point or last action that combines two smaller answers into the larger one.
The least you need to know
- An interval-DP state is typically `dp[l][r]` for a segment or subarray between endpoints `l` and `r`.
- Many interval DPs fill states by increasing segment length so smaller subintervals are ready first.
- A split point `k` often divides a segment into left and right subproblems.
- Some problems instead choose the last cut or last balloon, which still produces smaller remaining intervals.
- Base cases for empty or single-element intervals must match the recurrence exactly.
Key notation
dp[l][r]
best answer for the interval from `l` to `r`
length = r-l+1
order in which states are often filled
k
split point or last action inside the interval
Tiny worked example
- In matrix-chain multiplication, `dp[l][r]` is the minimum cost to multiply matrices from `l` to `r`.
- The recurrence tries every split point `k`, combining the left interval, the right interval, and the cost of joining them.
- Because those smaller intervals are shorter, filling by length works naturally.
Common mistakes
- Students often try prefix-style DP on problems whose natural state is a whole interval.
- The split point is not extra work for its own sake; it represents the structural choice inside the segment.
- Off-by-one mistakes in interval endpoints and base cases are the most common source of bugs.
How to recognize this kind of problem
- The prompt asks about removing, combining, or optimizing over contiguous segments.
- A single prefix index feels too weak because both ends of the current segment matter.
- The explanation talks about choosing where to cut or which interior action happens last.