Palindrome & Interval DP

Interval DP works on a contiguous range [i, j] of one string or array. Either you shrink the range from its ends (palindromes), or you split it at some point k and combine the two sides (burst balloons, cutting a stick, triangulating a polygon). Both shapes use the same state: the pair of ends.

The idea#

Shrink from both ends. For palindromes, only the two extreme characters matter at each step. If s[i] == s[j], they can be the outer pair of a palindrome, worth 2 plus whatever palindrome fits inside [i+1, j-1]. If they differ, at least one of them isn't used. So drop the left one or the right one and keep the better result.

Split at a point. For "split into parts" problems, try every split point k inside the range and take the best cost(i, k) + cost(k, j) + combine. The trick is choosing a k that makes the two sides independent. Often that means k is the last action to happen in the range, not the first.

Both shapes are correct for the same reason: each range depends only on strictly shorter ranges. Once the two sides are independent, the best answer for the range is the best over every k.

How to spot it#

Look for these signals in the question.

Palindromes: longest palindromic subsequence, palindromic substrings, minimum cuts.
"Split into parts", "merge adjacent", "cut", "burst", "triangulate": the cost of a step depends on its neighbors.
n up to a few hundred, since the split version is $O(n^3)$ .

Template#

Here is the shrink shape, used for palindromes. Generating every subsequence is exponential; working from the two ends inward is $O(n^2)$ .

solve(i, j):
    if i > j: return 0            # pointers crossed: empty range
    if i == j: return 1           # one element
    if s[i] == s[j]:
        return 2 + solve(i + 1, j - 1)    # both ends join
    return max(solve(i + 1, j),           # drop the left end
               solve(i, j - 1))           # drop the right end
memoize solve on (i, j)
answer: solve(0, n - 1)

The split shape#

The second shape is for "split into parts" problems. Try every k strictly inside the range, and choose k so its cost depends only on the range ends, not on what happened inside.

best(i, j):                       # work strictly between i and j
    result = 0 if nothing lies between i and j
    for each k from i + 1 to j - 1:
        result = best of (result,
                          best(i, k) + cost of k given i and j + best(k, j))
    return result
memoize best on (i, j); padding the ends often helps

If you write either shape bottom-up, fill by increasing range length. Each dp[i][j] needs shorter ranges first.

Pitfalls#

These mistakes cause the most wrong answers.

Splitting on an action whose neighbors change as the sides shrink. The subproblems are then not independent.
Missing the i > j base case. With an even-length palindrome, i + 1 > j - 1 happens and must return 0.
Filling a bottom-up table row by row from the top. Fill by increasing length (or i from the bottom, j from left to right).
Using split positions in the order given. The range ends must be in sorted order.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Longest Palindromic Subsequence

This is the shrink template as written. Equal ends add 2; unequal ends drop one side.

Hint: Palindromic Substrings

For contiguous substrings, expand around each of the 2n - 1 centers. That is $O(n^2)$ time and $O(1)$ space. The DP form is_pal(i, j) = s[i] == s[j] and is_pal(i+1, j-1) gives the same result.

Hint: Longest Palindromic Substring

Expand around every center, as in Palindromic Substrings, and keep the longest span you find.

Hint: Palindrome Partitioning II

Precompute the is_pal table first. Then cuts(i) is the fewest cuts for s[i:]: 0 if s[i:] is already a palindrome, else 1 + min(cuts(j + 1)) over every j where s[i..j] is a palindrome.

Hint: Burst Balloons

Pad the array with a 1 at each end. In the open range (i, j), pick the balloon k burst last. Its neighbors at that moment are exactly vals[i] and vals[j], so it earns vals[i] * vals[k] * vals[j]. Picking the first balloon fails: its neighbors change as the sides shrink.

Hint: Minimum Cost to Cut a Stick

Sort the cuts, and add 0 and n as ends. The state is a pair of cut positions. The first cut in a piece costs the piece's length.

Hint: Minimum Score Triangulation of Polygon

This is the matrix-chain shape: dp(i, j) = min(dp(i, k) + dp(k, j) + v[i]*v[k]*v[j]).

Key takeaways#

State = the two ends of a range.
Palindromes: compare the extremes; equal adds 2, unequal drops one end.
Split problems: try every k, and pick k so the two sides are independent ("last to happen").
Fill tables by increasing range length.

Core idea#

Interval DP works on a contiguous range [i, j], and the state is the pair of ends. Shrink the range from its ends (palindromes), or split it at a point k and combine the two sides.

Key points#

Palindromes: if s[i] == s[j], add 2 to the answer for [i+1, j-1]. If not, drop one end and keep the better result.
Split problems: try every k and take the best cost(i, k) + cost(k, j) + combine.
Pick k so the two sides are independent. In Burst Balloons, k is the last balloon to burst.
With k burst last in (i, j), its neighbors are exactly vals[i] and vals[j].
Spot it: palindromes, "split", "merge adjacent", "cut", "burst", "triangulate".
The split version is $O(n^3)$ , so n is up to a few hundred.

Variations#

Problem	Approach
Palindromic substrings	Expand around `2n - 1` centers: $O(n^2)$ time, $O(1)$ space
Palindrome Partitioning II	Precompute `is_pal`; `cuts(i) = 1 + min(cuts(j + 1))`
Min Cost to Cut a Stick	Sort cuts, add `0` and `n`; first cut costs the piece length
Min Score Triangulation	`min(dp(i, k) + dp(k, j) + v[i]v[k]v[j])`

Template#

solve(i, j):
    if i > j: return 0            # pointers crossed
    if i == j: return 1
    if s[i] == s[j]: return 2 + solve(i + 1, j - 1)
    return max(solve(i + 1, j), solve(i, j - 1))
split shape: best(i, j) = best over k of
    best(i, k) + cost of k given i and j + best(k, j)
memoize on (i, j); bottom-up, fill by increasing length

Pitfalls#

Choosing the first balloon to burst. Its neighbors change, so the sides are not independent.
Missing the i > j base case. Even-length palindromes reach it.
Filling a bottom-up table row by row from the top. Fill by increasing range length.
Forgetting to sort the cut positions.

Say it in an interview#

"The state is the two ends of the range."
"Choose the balloon burst last, so the two sides never affect each other."