Remove Boxes

Remove Boxes is one of the hardest interval-DP problems out there. What makes it special is that two indices are not enough to describe a subproblem — you need a third dimension that remembers how many equal boxes are already glued to the left. Once you see why, it becomes a clean recurrence.

The slow way first

A greedy try — always burst the biggest available run — fails. In [1, 3, 2, 3, 1] the best 1-run looks tiny at first, but if you clear the middle the 1s collide into a run of three worth 9. So the move that pays off depends on what you do later. That screams dynamic programming over intervals.

The trap: a plain dp(l, r) over a sub-array is not enough. Whether it is worth merging the boxes at l with a later equal box depends on how many equal boxes were already sitting to the left, outside this interval. Two numbers cannot capture that, so the state must carry a third value.

The idea: add a third dimension k

Define dp(l, r, k) = the best points obtainable from boxes[l..r] given that k extra boxes equal to boxes[l] are already attached on the left. At box l you have two moves:

• Pop now: burst the run of k + 1 equal boxes immediately for (k + 1)^2 points, then solve dp(l + 1, r, 0).
• Merge later: keep the run, find some m > l with boxes[m] == boxes[l], clear everything strictly between them with dp(l + 1, m - 1, 0), and that gluing lets the equal boxes join — solve dp(m, r, k + 1).

The whole point of k is the merge branch: it lets us defer popping the left run so a later equal box can join it, turning two small bursts into one big one.

Walk through it

Step through the animation on [1, 3, 2, 3, 1]. We start at dp(0, 4, 0). Option A pops the lone 1 for 1 point. Option B spots the matching 1 at index 4, clears the inside [3, 2, 3] (the two 3s merge for 4, plus 1 for the 2), then the two 1s become adjacent and burst together. Comparing the branches, merging wins — and the same reasoning across all intervals gives 13.

Pseudocode

define dp(l, r, k):                     # k = equal boxes glued left of l
    if l > r: return 0
    absorb equal neighbours: while boxes[l+1] == boxes[l]: l += 1; k += 1
    best = (k + 1)^2 + dp(l + 1, r, 0)  # option A: pop the left run now
    for m from l+1 to r:                # option B: merge with a later equal box
        if boxes[m] == boxes[l]:
            best = max(best, dp(l+1, m-1, 0) + dp(m, r, k+1))
    return best
answer = dp(0, n - 1, 0)

The Python solution

def remove_boxes(boxes):
    from functools import lru_cache
    n = len(boxes)
 
    @lru_cache(maxsize=None)
    def dp(l, r, k):
        if l > r:
            return 0
        while l < r and boxes[l + 1] == boxes[l]:
            l, k = l + 1, k + 1
        best = (k + 1) ** 2 + dp(l + 1, r, 0)
        for m in range(l + 1, r + 1):
            if boxes[m] == boxes[l]:
                inside = dp(l + 1, m - 1, 0)
                joined = dp(m, r, k + 1)
                best = max(best, inside + joined)
        return best
 
    return dp(0, n - 1, 0)

• dp(l, r, k) is the subproblem: solve boxes[l..r] with k equal boxes already glued to the left.
• The while loop absorbs equal neighbours into the left run up front, so boxes[l] starts a fresh color and k counts the whole run minus one.
• Line 11 is option A — pop the k + 1 glued boxes now for (k + 1)^2, then solve the rest from scratch.
• Lines 14-16 are option B — for each later box of the same color, clear the inside and recurse with k + 1 so the equal boxes merge; keep the better total.
• @lru_cache memoizes the three-argument state, turning exponential recursion into polynomial time.

Complexity

It looks heavy, but n is small for this problem, and memoization keeps it from blowing up. The lesson is the modeling move: when two interval endpoints cannot describe a subproblem, add a dimension that captures the missing context.

When this pattern shows up

Practice