Interval DP

The recognition signal

Interval DP is the pattern to reach for when a problem asks you to optimize some value over contiguous ranges of an array or string, and the natural recursive idea is: "pick a split point inside this range, solve the two halves independently, then combine them." If you catch yourself thinking "what if I try every way to split this range into two smaller ranges" — that's the tell. It's a genuinely different shape from everything else in this topic, which is why it's rated the highest difficulty subtopic here despite having the shortest theory time: the recurrence itself isn't more complex than 2-D DP, but the iteration order is the first thing in this roadmap that breaks the "just go in increasing index order" instinct you've built up.

State definition and the core recurrence

State: dp[i][j] = the optimal (min or max) value achievable over the range/interval [i, j] (inclusive on both ends, by convention).

Transition: try every possible split/operation point k inside [i, j], and combine the optimal answers for the two resulting sub-ranges plus a cost specific to this merge:

$$dp[i][j] = \min_{i \le k < j} \Big( dp[i][k] + dp[k+1][j] + \text{cost}(i, k, j) \Big)$$

This is structurally the "matrix chain multiplication" shape: given a chain of matrices, the optimal way to parenthesize their multiplication is found by trying every split point k, solving the cost of multiplying the left group [i..k] and right group [k+1..j] optimally, and adding the cost of the final multiplication that combines the two resulting matrices. It's a clean, canonical illustration of the pattern — deliberately not one of your listed problems — worth internalizing on its own:

The same "burst a balloon / remove an element and pay a cost that depends on its current neighbors"-style problems you'll drill in this subtopic all reduce to picking which element is dealt with last (rather than first) within a range — a reframing that turns an order-dependent process into one where the two resulting sub-ranges genuinely become independent subproblems. Recognizing that reframing — "what if I decide the last operation in this range, not the first" — is often the single insight that unlocks an interval DP problem; it's worth trying deliberately whenever the naive "process left to right" framing produces sub-ranges that still depend on each other.

Why you must iterate by increasing interval length

This is the detail that makes Interval DP feel different from everything before it: dp[i][j]'s dependencies are dp[i][k] and dp[k+1][j] for k strictly between i and j — both of which are shorter intervals, but neither of which has a fixed relationship to "smaller i" or "smaller j" the way earlier topics did. A row-major or column-major fill (the natural order for grid DP) will read cells that haven't been computed yet.

The fix: iterate by increasing interval length first, and by starting index second. Every sub-interval of a given length was necessarily already computed in an earlier pass, because it's shorter.

Contrast this explicitly with the grid-path and two-string DP from the previous subtopic, where row-major order was always safe because dependencies were strictly "one row up" or "one column left." Here there is no such fixed direction — the length of the interval is the only quantity that decreases monotonically toward the base case, which is exactly why it has to be the outer loop variable.

Base cases

The base case is almost always the smallest meaningful interval — typically length 1 (dp[i][i], a single element, usually costing 0 or the value of that single element) — and sometimes you also need length-0 ("empty interval between two adjacent split points") initialized to a neutral value (0 for a sum/cost, or a sentinel for a boolean feasibility check). Get this wrong and every larger interval inherits the error, since every dp[i][j] transitively depends on the base cases through the split-point recursion.

Comparison: interval DP vs. the DP you've seen so far

	1-D / Knapsack / 2-D string DP	Interval DP
State represents	A prefix, a position, or a pair of prefixes	A contiguous range [i, j]
Transition looks at	A constant number of smaller states, or a full backward scan	Every possible split point k inside the range
Safe iteration order	Increasing index (row-major for 2-D)	Increasing interval length, then start index
Typical transition cost per state	O(1) or O(n)	O(range length) — you try every split point
Overall complexity	O(n) to O(n²)	Typically O(n³)

Complexity

State space is O(n²) (all pairs i ≤ j), and each state's transition tries O(n) split points, giving O(n³) time overall for the standard formulation — noticeably worse than anything earlier in this topic, and worth stating out loud as soon as you recognize the pattern, since it directly affects what input sizes are tractable (n in the few hundreds is typically the practical ceiling for an O(n³) interview solution). Space is O(n²) for the table. Advanced optimizations exist to bring specific interval DP recurrences down to O(n²) (Knuth's optimization, when the cost function satisfies certain monotonicity properties) — good to know exists, rarely required to derive from scratch in a Senior-level interview, but a strong signal if you can name it when a problem's constraints (n up to 10⁴–10⁵) make plain O(n³) too slow.

Common pitfalls

• Row-major / column-major iteration — by far the most common bug in this subtopic. If you write your loops the way you would for grid DP, you will read uncomputed cells and get silently wrong (usually zero or garbage) values. Always iterate by length first.
• Off-by-one in interval bounds. Decide up front whether dp[i][j] is inclusive of both endpoints (most common convention) and be consistent; the split-point loop range (k from i to j-1, or i to j, depending on whether k belongs to the left or right sub-range) is a frequent source of subtle bugs.
• Missing or wrong base case for length-1 (or length-0) intervals, especially forgetting that some problems need an explicit "empty range between adjacent split points" case, not just single-element ranges.
• Not reframing "process left-to-right" problems as "decide what happens last." If your sub-ranges after a naive split still interact with each other, you likely haven't found the right split semantics yet — try reframing around the last operation in the range instead of the first.
• Ignoring the O(n³) complexity until it's too late. If you don't state the complexity as you derive the recurrence, you risk discovering only after coding it up that it won't fit the given constraints — costing you the time budget to consider an optimization or a different approach.