Problem Description

The Remove Boxes problem presents you with an array of integers called boxes, where each element represents the color of a box. The goal is to remove boxes from the array to maximize your score, following these rules:

• In one move, you can remove a contiguous group of boxes with the same color.
• When you remove k adjacent boxes of the same color, you gain k * k points.
• The remaining boxes close up the gap (i.e., the array becomes shorter).
• You repeat this process until there are no boxes left.

Your task is to determine the maximum score you can achieve by removing the boxes in an optimal order. The constraints are:

• There is only one valid solution for each input.
• Each box can only be removed once.
• The length of boxes is up to 100.

Thought Process

At first glance, you might consider removing the largest group of same-colored boxes at each step (a greedy approach). However, this does not always yield the highest score, because sometimes it is better to leave a group for later to merge with other boxes of the same color, resulting in a much higher score due to the square function (k * k).

The brute-force approach would be to try every possible removal sequence, but the number of possibilities grows exponentially. To optimize, we need a way to remember the results of subproblems we've already solved, i.e., use dynamic programming with memoization. We need to track not just the subarray we are considering, but also how many boxes of the same color are contiguous to the left (to allow for merging).

Solution Approach

We use a 3D dynamic programming approach to solve this problem efficiently. Here’s how the solution is structured:

1. Define the DP State: Let dp[l][r][k] be the maximum score for the subarray boxes[l...r] with k boxes of the same color as boxes[r] appended to the right.
2. Base Case: If l > r, return 0 (no boxes left).
3. Recursive Case:
   • First, try to remove the last group (ending at r) along with any extra boxes of the same color (k):
     • Compute dp[l][r-1][0] + (k+1)^2
   • Next, try to merge non-contiguous boxes of the same color. For every i from l to r-1 where boxes[i] == boxes[r]:
     • Remove boxes between i+1 and r-1 first, so that boxes[i] and boxes[r] become adjacent. Then, solve for dp[l][i][k+1] + dp[i+1][r-1][0].
   • Take the maximum over all options.
4. Memoization: Store results of subproblems in a 3D array or hash map to avoid redundant calculations.

This approach ensures that all possible merging and removal sequences are considered, but each unique subproblem is solved only once.

Example Walkthrough

Let's walk through an example with boxes = [1, 3, 2, 2, 2, 3, 4, 3, 1].

1. We can remove the group [2,2,2] (indices 2-4), earning 3*3=9 points. The array becomes [1,3,3,4,3,1].
2. Now, we have two 3s separated by 4. If we remove 4 first, we can merge the 3s into a group of 3, earning 3*3=9 points.
3. Continue this process, always considering whether it's better to merge non-contiguous boxes of the same color by removing intervening boxes first.
4. The DP ensures that the best sequence is found, possibly removing boxes in a non-greedy order to maximize the final score.

In this example, the optimal sequence gives a score of 23.

Time and Space Complexity

• Brute-force: The number of possible removal sequences is exponential, so the time complexity is O(n!).
• DP Solution: There are O(n^3) subproblems because l and r each range from 0 to n-1, and k can be up to n. Each subproblem takes O(n) time to compute (for the inner loop), so the total is O(n^4).
• Space Complexity: The memoization array uses O(n^3) space.

Summary

The Remove Boxes problem is a classic example of how dynamic programming can be used to optimize a seemingly intractable problem. By carefully defining the state and using memoization, we avoid redundant calculations and ensure that all possible merging and removal strategies are considered. The key insight is that sometimes, removing boxes in a non-greedy order allows for larger groups to be formed later, greatly increasing the score. This solution elegantly balances recursion, state tracking, and optimal substructure.

Code Implementation

from functools import lru_cache

class Solution:
    def removeBoxes(self, boxes):
        n = len(boxes)
        
        @lru_cache(None)
        def dp(l, r, k):
            if l > r:
                return 0
            # Extend boxes[r] group to the left
            while l < r and boxes[r] == boxes[r-1]:
                r -= 1
                k += 1
            # Option 1: remove the group at the end
            res = dp(l, r-1, 0) + (k+1)*(k+1)
            # Option 2: try to merge non-contiguous groups
            for i in range(l, r):
                if boxes[i] == boxes[r]:
                    res = max(res, dp(l, i, k+1) + dp(i+1, r-1, 0))
            return res
        
        return dp(0, n-1, 0)
      

class Solution {
public:
    int dp[100][100][100];
    int removeBoxes(vector<int>& boxes) {
        memset(dp, -1, sizeof(dp));
        return helper(boxes, 0, boxes.size() - 1, 0);
    }
    
    int helper(vector<int>& boxes, int l, int r, int k) {
        if (l > r) return 0;
        if (dp[l][r][k] != -1) return dp[l][r][k];
        int orig_r = r, orig_k = k;
        while (l < r && boxes[r] == boxes[r-1]) {
            r--;
            k++;
        }
        int res = helper(boxes, l, r-1, 0) + (k+1)*(k+1);
        for (int i = l; i < r; ++i) {
            if (boxes[i] == boxes[r]) {
                res = max(res, helper(boxes, l, i, k+1) + helper(boxes, i+1, r-1, 0));
            }
        }
        dp[l][orig_r][orig_k] = res;
        return res;
    }
};
      

class Solution {
    int[][][] dp;
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        dp = new int[n][n][n];
        return helper(boxes, 0, n-1, 0);
    }
    private int helper(int[] boxes, int l, int r, int k) {
        if (l > r) return 0;
        if (dp[l][r][k] != 0) return dp[l][r][k];
        while (l < r && boxes[r] == boxes[r-1]) {
            r--;
            k++;
        }
        int res = helper(boxes, l, r-1, 0) + (k+1)*(k+1);
        for (int i = l; i < r; i++) {
            if (boxes[i] == boxes[r]) {
                res = Math.max(res, helper(boxes, l, i, k+1) + helper(boxes, i+1, r-1, 0));
            }
        }
        dp[l][r][k] = res;
        return res;
    }
}
      

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