Remove Boxes

hard array dp memoization

Problem

Remove contiguous groups of equal boxes; a group of length L scores L². Return max total.

Inputboxes = [1,3,2,2,2,3,4,3,1]

Output23

Two cases: drop the leading run as (k+1)², OR merge with a matching later box to enlarge k.

boxes

def remove_boxes(boxes):
    from functools import lru_cache
    @lru_cache(None)
    def f(l, r, k):
        if l > r: return 0
        L, K = l, k
        while L + 1 <= r and boxes[L + 1] == boxes[L]: L += 1; K += 1
        ans = (K + 1) ** 2 + f(L + 1, r, 0)
        for i in range(L + 2, r + 1):
            if boxes[i] == boxes[L]:
                ans = max(ans, f(L + 1, i - 1, 0) + f(i, r, K + 1))
        return ans
    return f(0, len(boxes) - 1, 0)

function removeBoxes(boxes) {
  const n = boxes.length;
  const memo = new Map();
  function f(l, r, k) {
    if (l > r) return 0;
    const key = l + "," + r + "," + k;
    if (memo.has(key)) return memo.get(key);
    let L = l, K = k;
    while (L + 1 <= r && boxes[L + 1] === boxes[L]) { L++; K++; }
    let ans = (K + 1) * (K + 1) + f(L + 1, r, 0);
    for (let i = L + 2; i <= r; i++) {
      if (boxes[i] === boxes[L]) ans = Math.max(ans, f(L + 1, i - 1, 0) + f(i, r, K + 1));
    }
    memo.set(key, ans);
    return ans;
  }
  return f(0, n - 1, 0);
}

class Solution {
    int[][][] memo;
    int[] boxes;
    public int removeBoxes(int[] b) {
        boxes = b;
        int n = b.length;
        memo = new int[n][n][n];
        return f(0, n - 1, 0);
    }
    int f(int l, int r, int k) {
        if (l > r) return 0;
        if (memo[l][r][k] != 0) return memo[l][r][k];
        int L = l, K = k;
        while (L + 1 <= r && boxes[L + 1] == boxes[L]) { L++; K++; }
        int ans = (K + 1) * (K + 1) + f(L + 1, r, 0);
        for (int i = L + 2; i <= r; i++)
            if (boxes[i] == boxes[L]) ans = Math.max(ans, f(L + 1, i - 1, 0) + f(i, r, K + 1));
        return memo[l][r][k] = ans;
    }
}

int memo[101][101][101] = {};
vector bx;
int f(int l, int r, int k) {
    if (l > r) return 0;
    if (memo[l][r][k]) return memo[l][r][k];
    int L = l, K = k;
    while (L + 1 <= r && bx[L + 1] == bx[L]) { L++; K++; }
    int ans = (K + 1) * (K + 1) + f(L + 1, r, 0);
    for (int i = L + 2; i <= r; i++)
        if (bx[i] == bx[L]) ans = max(ans, f(L + 1, i - 1, 0) + f(i, r, K + 1));
    return memo[l][r][k] = ans;
}
int removeBoxes(vector& b) { bx = b; memset(memo, 0, sizeof(memo)); return f(0, b.size() - 1, 0); }

Explanation

Removing a run of L equal boxes scores L², so it pays to merge same-colored boxes together before removing them. The hard part is that the best merge depends on what you do with boxes in between, which is why this needs a clever 3D state.

We define f(l, r, k) as the max points from the segment boxes[l..r] when there are also k extra boxes equal to boxes[l] already glued to its left. That third parameter k is the trick: it lets us "carry" matching boxes forward so they can be removed together later.

First we extend the leading run: if boxes right after l equal boxes[l], we absorb them, growing the glued count K. Then there are two choices. Remove now: take the whole leading block of size K+1 for (K+1)² points and solve the rest. Or save for later: find a later box i with the same color, clear everything between, and recurse on f(i, r, K+1) so the matching boxes join up.

We keep the best of all these options and memoize each (l, r, k) so repeated subproblems are solved once.

Example: boxes = [1,3,2,2,2,3,4,3,1]. By saving the 3's and 1's to merge with their twins, the optimal score works out to 23.

Time: O(n⁴) Space: O(n³)