Hard

题目描述

给出一些不同颜色的盒子，颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续盒子序列（由 k 个盒子组成，k >= 1），这样的话就会获得 k * k 个积分。

返回你能获得的最大积分和。

示例 1：

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[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)

示例 2：

输入：boxes = [1,1,1]
输出：9

示例 3：

输入：boxes = [1]
输出：1

提示：

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

解题思路

这是一道经典的区间动态规划题目，核心思想是考虑如何合并相同颜色的盒子来获得最大得分。

基本思路： 使用记忆化递归的动态规划方法。定义 dp(i, j, k) 表示在区间 [i, j] 内移除所有盒子，且在位置 j 右边还有 k 个与 boxes[j] 相同颜色的盒子时能获得的最大得分。

状态转移：

  1. 如果 i > j，返回 0
  2. 先将 j 向左扩展，找到所有与 boxes[j] 相同颜色的连续盒子，统计数量
  3. 对于每个可能的分割点 m（其中 boxes[m] == boxes[j]），尝试两种策略：
    • 直接移除右边的相同颜色盒子：dp(i, j-1, 0) + (k+1)*(k+1)
    • 先移除中间部分，再合并相同颜色：dp(i, m, k+1) + dp(m+1, j-1, 0)

优化要点：

  • 使用记忆化避免重复计算
  • 预处理相同颜色的连续盒子以减少状态数量
  • 三维DP的状态设计是关键，第三维k表示右边等待合并的相同颜色盒子数量

时间复杂度为 O(n³)，空间复杂度为 O(n³)，其中 n 是盒子数量。

代码实现

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, -1)));
        return dp(boxes, 0, n - 1, 0, memo);
    }
    
private:
    int dp(vector<int>& boxes, int i, int j, int k, vector<vector<vector<int>>>& memo) {
        if (i > j) return 0;
        if (memo[i][j][k] != -1) return memo[i][j][k];
        
        // 将j向左扩展，找到所有相同颜色的连续盒子
        while (i <= j - 1 && boxes[j] == boxes[j - 1]) {
            j--;
            k++;
        }
        
        // 直接移除boxes[j]及其右边的k个相同颜色盒子
        int result = dp(boxes, i, j - 1, 0, memo) + (k + 1) * (k + 1);
        
        // 尝试与左边的相同颜色盒子合并
        for (int m = i; m < j; m++) {
            if (boxes[m] == boxes[j]) {
                result = max(result, 
                    dp(boxes, i, m, k + 1, memo) + dp(boxes, m + 1, j - 1, 0, memo));
            }
        }
        
        return memo[i][j][k] = result;
    }
};

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        n = len(boxes)
        memo = {}
        
        def dp(i, j, k):
            if i > j:
                return 0
            if (i, j, k) in memo:
                return memo[(i, j, k)]
            
            # 将j向左扩展，找到所有相同颜色的连续盒子
            orig_j = j
            while j > i and boxes[j] == boxes[j - 1]:
                j -= 1
                k += 1
            
            # 直接移除boxes[j]及其右边的k个相同颜色盒子
            result = dp(i, j - 1, 0) + (k + 1) * (k + 1)
            
            # 尝试与左边的相同颜色盒子合并
            for m in range(i, j):
                if boxes[m] == boxes[j]:
                    result = max(result, 
                        dp(i, m, k + 1) + dp(m + 1, j - 1, 0))
            
            memo[(i, orig_j, k)] = result
            return result
        
        return dp(0, n - 1, 0)

public class Solution {
    private int[,,] memo;
    
    public int RemoveBoxes(int[] boxes) {
        int n = boxes.Length;
        memo = new int[n, n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    memo[i, j, k] = -1;
                }
            }
        }
        return Dp(boxes, 0, n - 1, 0);
    }
    
    private int Dp(int[] boxes, int i, int j, int k) {
        if (i > j) return 0;
        if (memo[i, j, k] != -1) return memo[i, j, k];
        
        // 将j向左扩展，找到所有相同颜色的连续盒子
        while (i <= j - 1 && boxes[j] == boxes[j - 1]) {
            j--;
            k++;
        }
        
        // 直接移除boxes[j]及其右边的k个相同颜色盒子
        int result = Dp(boxes, i, j - 1, 0) + (k + 1) * (k + 1);
        
        // 尝试与左边的相同颜色盒子合并
        for (int m = i; m < j; m++) {
            if (boxes[m] == boxes[j]) {
                result = Math.Max(result, 
                    Dp(boxes, i, m, k + 1) + Dp(boxes, m + 1, j - 1, 0));
            }
        }
        
        return memo[i, j, k] = result;
    }
}

var removeBoxes = function(boxes) {
    const n = boxes.length;
    const memo = new Map();
    
    function dp(i, j, k) {
        if (i > j) return 0;
        
        const key = `${i},${j},${k}`;
        if (memo.has(key)) return memo.get(key);
        
        // 将j向左扩展，找到所有相同颜色的连续盒子
        const origJ = j;
        while (j > i && boxes[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n³)
空间复杂度O(n³)

其中 n 为盒子数量。时间复杂度来自于三重循环的状态转移，空间复杂度来自于三维记忆化数组。

相关题目