Palindrome Removal

Palindrome Removal is a classic interval DP problem. It teaches the core interval-DP move: build answers for small ranges first, then combine them into bigger ranges, with a special bonus whenever the two ends of a range match.

The slow way first

You could try every possible sequence of removals by brute force, but the number of ways to choose and order palindromic deletions explodes combinatorially. That is far too slow.

The question to ask: what is the smallest piece of the problem whose answer is obvious, and how do I build up from there? A single element is always a palindrome, so clearing it costs exactly one move. That tiny fact is the seed for everything else.

The idea: solve every interval, shortest first

Let dp[l][r] be the minimum moves to clear the subarray a[l..r]. Build it up by interval length. For a range:

• By default, split it: dp[l][r] = min over k of dp[l][k] + dp[k+1][r]. Clear the left part, then the right.
• Bonus when a[l] == a[r]: the two equal ends can be carried out together with whatever palindrome clears the inside, so dp[l][r] may also take dp[l+1][r-1].

Because every range is built from strictly shorter ranges, filling intervals in increasing length guarantees the pieces we need are already computed.

Walk through it

Step through the animation. First the length-1 intervals are seeded to 1. Then a full interval a[0..4] whose ends differ (1 vs 5) is solved purely by splitting. Finally the interval a[0..3] whose ends match (1 and 1) gets the discount: it may ride along with the inside dp[1][2]. The final answer lives in dp[0][n-1].

Pseudocode

dp = n x n table
for each i:
    dp[i][i] = 1                       # one element is one removal
for length in 2..n:
    for each interval [l, r] of that length:
        dp[l][r] = dp[l][r-1] + 1      # start: clear last, then the rest
        for each split point k in [l, r):
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r])
        if a[l] == a[r]:               # matching ends -> discount
            inner = dp[l+1][r-1] if the inside exists else 0
            dp[l][r] = min(dp[l][r], max(inner, 1))
return dp[0][n-1]

The Python solution

def min_removals(a):
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            dp[l][r] = dp[l][r - 1] + 1
            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r])
            if a[l] == a[r]:
                inner = dp[l + 1][r - 1] if r - l >= 2 else 0
                dp[l][r] = min(dp[l][r], max(inner, 1))
    return dp[0][n - 1]

• dp[i][i] = 1 seeds every single element: one move clears it.
• We iterate by length so shorter intervals are always solved before longer ones depend on them.
• dp[l][r] = dp[l][r-1] + 1 is a safe starting guess: clear a[l..r-1], then spend one move on a[r].
• The split loop tries every cut point k, combining two already-solved halves.
• The a[l] == a[r] branch is the interval-DP discount: matching ends remove together with the inside, so dp[l][r] can drop to max(inner, 1).
• The answer is dp[0][n-1] — the whole array.

Complexity

The O(n²) space is the DP table itself — one cell for every interval. The cubic time comes from trying every split point inside every interval.

When this pattern shows up

Practice