1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/remove-boxes/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义。dp[i][j][k]表示boxes的[i,j]区间和右侧k个与boxes[j]相同的元素组成的子问题下的最大积分和

第二步，状态初始化。当i>j时，dp[i][j][*]=0，初始化时全部设置为0

第三步，状态转移。记previewPoints=dp[i][j-1][0]，表示单独[i,j-1]区间进行移除的子问题下的最大积分和，其中当i==j时previewPoints=0；转移方程dp[i][j][k]=max(prevPoints+(k+1)*(k+1), max(dp[i][m][k+1]+dp[m+1][j-1][0] for m in range(i,j) if boxes[m]==boxes[j]))，其中k的范围为0到n-j-1，这里枚举的是k的可能，实际的移除情况会包含在这些可能中。由于dp[i][j][k]依赖的状态的区间都比[i,j]区间的长度小，所以考虑使用区间动态规划

第四步，最终的dp[0][n-1][0]即为题解

3.解题代码

python代码

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        # 思路：动态规划
        n = len(boxes)
        # 第一步，状态定义。dp[i][j][k]表示boxes的[i,j]区间和右侧k个与boxes[j]相同的元素组成的子问题下的最大积分和
        dp = [[[0] * n for _ in range(n)] for _ in range(n)]
        # 第二步，状态初始化。当i>j时，dp[i][j][*]=0，初始化时全部设置为0
        # 第三步，状态转移。记previewPoints=dp[i][j-1][0]，表示单独[i,j-1]区间进行移除的子问题下的最大积分和，其中当i==j时previewPoints=0；转移方程dp[i][j][k]=max(prevPoints+(k+1)*(k+1), max(dp[i][m][k+1]+dp[m+1][j-1][0] for m in range(i,j) if boxes[m]==boxes[j]))，其中k的范围为0到n-j-1，这里枚举的是k的可能，实际的移除情况会包含在这些可能中。由于dp[i][j][k]依赖的状态的区间都比[i,j]区间的长度小，所以考虑使用区间动态规划
        for subLen in range(1, n + 1):
            for i in range(n - subLen + 1):
                j = i + subLen - 1
                maxCount = n - j - 1
                prevPoints = dp[i][j - 1][0] if i < j else 0
                for k in range(maxCount + 1):
                    maxPoints = prevPoints + (k + 1) * (k + 1)
                    for m in range(i, j):
                        if boxes[m] == boxes[j]:
                            maxPoints = max(maxPoints, dp[i][m][k + 1] + dp[m + 1][j - 1][0])
                    dp[i][j][k] = maxPoints
        # 第四步，最终的dp[0][n-1][0]即为题解
        return dp[0][n - 1][0]

c++代码

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        vector<vector<vector<int>>> dp(n, vector(n, vector(n, 0)));
        for (int subLen = 1; subLen <= n; subLen++) {
            for (int i = 0; i <= n - subLen; i++) {
                int j = i + subLen - 1;
                int maxCnt = n - j - 1;
                for (int k = 0; k <= maxCnt; k++) {
                    int prevPoints = i < j ? dp[i][j - 1][0] : 0;
                    int maxPoints = prevPoints + (k + 1) * (k + 1);
                    for (int m = i; m < j; m++) {
                        if (boxes[m] == boxes[j]) {
                            maxPoints = max(maxPoints, dp[i][m][k + 1] + dp[m + 1][j - 1][0]);
                        }
                    }
                    dp[i][j][k] = maxPoints;
                }
            }
        }
        return dp[0][n - 1][0];
    }
};

4.执行结果