Leetcode 546: Remove Boxes

You are given several boxes with different colors represented by different positive numbers.

You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= 1), remove them and get k * k points.

Return the maximum points you can get.

Example 1:

Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

Example 2:

Input: boxes = [1,1,1]
Output: 9

Example 3:

Input: boxes = [1]
Output: 1

Constraints:

• 1 <= boxes.length <= 100
• 1 <= boxes[i] <= 100

Problem Analysis:

As we can see every time we remove boxes, we can remove continuous boxes with some color, so we can use depth first search to iterate removing. For avoid repeated operations, we can use memory to record previous operation results.

So how do we iterate removing? Suppose we want to remove boxes of range [i, j], assume the boxes in range [r, j] is continuous, then we iterate the range [i, r-1] to find whether exists some range [m, n], i ≤ m ≤ n < r, that have the same color with boxes[j]. If so, we can first try to remove range [n+1, r— 1] to make range [m, n] and [r, j] become continuous.

So iterate the operation until we remove all boxes. we can compute the maximum points.

Solution

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {    
        vector<vector<vector<int>>> data(boxes.size(), vector<vector<int>>(boxes.size(), vector<int>(boxes.size(), 0)));
        function<int(int, int, int)> dfs = [&](int left, int right, int k) {
            if (left > right) return 0;
            if (data[left][right][k] > 0) return data[left][right][k];
            
            int rr{right};
            while (left < right && boxes[right - 1] == boxes[right]) {
                --right;
                ++k;
            }
            data[left][right][k] = dfs(left, right - 1, 0) + (k + 1) * (k + 1);
            for (int i = left; i < right; ++i) {
                if (boxes[i] == boxes[right]) {
                    data[left][right][k] = 
                        max(data[left][right][k], dfs(left, i, k + 1) + dfs(i + 1, right - 1, 0));
                }
            }
            for (int i = 1; i <= rr - right; ++i) 
                data[left][right + i][k - i] = data[left][right][k];
            return data[left][right][k];
        };
        return dfs(0, boxes.size() - 1, 0);
    }
};

time complexity is O(boxes³)

Space complexity is O(boxes³)