546. Remove Boxes

Problem Description

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,4,3,1] --> [1,3,3,3,1] (1*1=1 points)
[1,3,3,3,1] --> [1,1] (3*3=9 points)
[1,1] --> [] (2*2=4 points)
Total points = 9 + 1 + 9 + 4 = 23

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

Python Solution

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dp(l: int, r: int, k: int) -> int:
            if l > r:
                return 0
            
            # Skip repeated boxes to optimize
            while l + 1 <= r and boxes[l] == boxes[l + 1]:
                l += 1
                k += 1
            
            # Remove current group of boxes
            result = (k + 1) * (k + 1) + dp(l + 1, r, 0)
            
            # Try to merge non-adjacent same colored boxes
            for i in range(l + 1, r + 1):
                if boxes[i] == boxes[l]:
                    result = max(result, dp(l + 1, i - 1, 0) + dp(i, r, k + 1))
            
            return result
        
        return dp(0, len(boxes) - 1, 0)

Java Solution

class Solution {
    private int[][][] memo;
    private int[] boxes;
    
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        this.boxes = boxes;
        this.memo = new int[n][n][n];
        return dp(0, n - 1, 0);
    }
    
    private int dp(int l, int r, int k) {
        if (l > r) return 0;
        if (memo[l][r][k] > 0) return memo[l][r][k];
        
        // Skip repeated boxes
        int origL = l, origK = k;
        while (l + 1 <= r && boxes[l] == boxes[l + 1]) {
            l++;
            k++;
        }
        
        // Remove current group
        int result = (k + 1) * (k + 1) + dp(l + 1, r, 0);
        
        // Try merging non-adjacent boxes
        for (int i = l + 1; i <= r; i++) {
            if (boxes[i] == boxes[l]) {
                result = Math.max(result, dp(l + 1, i - 1, 0) + dp(i, r, k + 1));
            }
        }
        
        memo[origL][r][origK] = result;
        return result;
    }
}

C++ Solution

class Solution {
private:
    vector>> memo;
    vector boxes;
    
    int dp(int l, int r, int k) {
        if (l > r) return 0;
        if (memo[l][r][k] > 0) return memo[l][r][k];
        
        // Skip repeated boxes
        int origL = l, origK = k;
        while (l + 1 <= r && boxes[l] == boxes[l + 1]) {
            l++;
            k++;
        }
        
        // Remove current group
        int result = (k + 1) * (k + 1) + dp(l + 1, r, 0);
        
        // Try merging non-adjacent boxes
        for (int i = l + 1; i <= r; i++) {
            if (boxes[i] == boxes[l]) {
                result = max(result, dp(l + 1, i - 1, 0) + dp(i, r, k + 1));
            }
        }
        
        return memo[origL][r][origK] = result;
    }
    
public:
    int removeBoxes(vector& boxes) {
        int n = boxes.size();
        this.boxes = boxes;
        memo = vector>>(n, vector>(n, vector(n)));
        return dp(0, n - 1, 0);
    }
};

JavaScript Solution

/**
 * @param {number[]} boxes
 * @return {number}
 */
var removeBoxes = function(boxes) {
    const n = boxes.length;
    const memo = Array(n).fill().map(() => 
        Array(n).fill().map(() => Array(n).fill(0)));
    
    const dp = (l, r, k) => {
        if (l > r) return 0;
        if (memo[l][r][k] > 0) return memo[l][r][k];
        
        // Skip repeated boxes
        let origL = l, origK = k;
        while (l + 1 <= r && boxes[l] === boxes[l + 1]) {
            l++;
            k++;
        }
        
        // Remove current group
        let result = (k + 1) * (k + 1) + dp(l + 1, r, 0);
        
        // Try merging non-adjacent boxes
        for (let i = l + 1; i <= r; i++) {
            if (boxes[i] === boxes[l]) {
                result = Math.max(result, dp(l + 1, i - 1, 0) + dp(i, r, k + 1));
            }
        }
        
        memo[origL][r][origK] = result;
        return result;
    };
    
    return dp(0, n - 1, 0);
};

C# Solution

public class Solution {
    private int[][][] memo;
    private int[] boxes;
    
    public int RemoveBoxes(int[] boxes) {
        int n = boxes.Length;
        this.boxes = boxes;
        memo = new int[n][][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[n][];
            for (int j = 0; j < n; j++) {
                memo[i][j] = new int[n];
            }
        }
        return DP(0, n - 1, 0);
    }
    
    private int DP(int l, int r, int k) {
        if (l > r) return 0;
        if (memo[l][r][k] > 0) return memo[l][r][k];
        
        // Skip repeated boxes
        int origL = l, origK = k;
        while (l + 1 <= r && boxes[l] == boxes[l + 1]) {
            l++;
            k++;
        }
        
        // Remove current group
        int result = (k + 1) * (k + 1) + DP(l + 1, r, 0);
        
        // Try merging non-adjacent boxes
        for (int i = l + 1; i <= r; i++) {
            if (boxes[i] == boxes[l]) {
                result = Math.Max(result, DP(l + 1, i - 1, 0) + DP(i, r, k + 1));
            }
        }
        
        memo[origL][r][origK] = result;
        return result;
    }
}