546. 移除盒子

题目

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。

示例：

输入：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 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)

提示：

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

解题思路

思路：动态规划

首先先看题目，题目给定一组序列，里面不同的数字代表着不同颜色的盒子。题目要求移除盒子，求得序列为空，也就是移除掉所有盒子时能获得的最大积分。

在这里，积分的计算方式如下（移除盒子的操作次数不限）：

当移除的盒子是具有相同颜色的，假设为 k（k>=1） 个，那么此时获得得积分为 k * k。

现在，我们结合例子来看，

输入：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 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)

这里大致说下解释中的部分：

• 首先移除的是 3 个 2，积分为 3*3=9；
• 再是移除的是 1 个 4，积分为 1*1=9；
• 然后移除的是 3 个 3，积分为 3*3=9；
• 最后移除的是 2 个 1，积分为 2*2=4。

在这里，我们可以看到当移除某个颜色的盒子之后，序列会发生变化，也就说，原本并非相连的盒子，后续也会变成连续的相同颜色盒子。

那么现在的问题就是，如何找到能够在移除盒子后，构成连续相同的盒子，从而获得更多积分的策略。

状态定义

参考官方题解，默认在区间 [l, r] 消除 boxes[r]

前面说明了，因为移除盒子后，对当前的序列是有影响的。那么我现在就不能单纯的设定 dp[l][r] 表示移除区间 [l, r] 内盒子能获得的最大积分。在这里，我们还需要一个参数 k 来标记状态，这个 k 表示的后面存在 k 个与 boxes[r] 相同颜色的盒子个数。

那么设 dp[l][r][k] 表示从区间 [l, r] 移除相同颜色的盒子， r 右边有 k 个和 boxes[r] 相同颜色的盒子的积分。

下面用图来说明下，有助于理解。假设拥有以下序列。

现在假设先将数字 4 代表的盒子移除，如下：

那么，就剩下部分序列中，对于移除数字 2 代表的盒子，我们有两个策略：

• 1. 将此时 3 个连接的盒子（数字 2 代表的盒子）先移除掉；
• 1. 将此时 3 个盒子先当做整体，删除数字 3 代表的盒子，与前面相同颜色的盒子组合。

此时，序列如下：

先看策略一，移除此时相连颜色相同的 3 个盒子（数字 2）

那么剩下序列如下：

此时上面的序列积分表现方式为：dp[0][3][0]，也就说当前策略的积分为：dp[0][3][0] + 3x3。

再看第二种策略，将后面连续的当成整体，在前面找到与 boxes[r] 颜色相同的盒子，移除掉中间的盒子。

下面红色虚线部分，表示找到与 boxes[r] 相同的盒子

那么现在将中间黄色部分的盒子移除，对应能获得的积分为 dp[3][3][0]

此时剩下的序列为 dp[0][2][3]：

那么此时策略二的积分为：dp[0][2][3] + dp[3][3][0]。

比较两个策略，去积分值大的策略积分所得。

状态转移方程

现在，就上面的图示分析进行总结：

• 策略一：

  • 在区间 [l, r] 中，先移除右边与 boxes[r] （包括 boxes[r]）相同的 k+1 个盒子，然后在考虑移除区间 [l, r-1] 的盒子；
  • 那么此时的转移方程为：dp[l][r][k] = dp[l][r-1][0] + (k+1)*(k+1)。

• 策略二：

  • 在区间 [l, r] 之间，将 boxes[r] 这个盒子与后面相同颜色的盒子当成是一个整体。然后在 [l, r-1] 这个区间中进行遍历，找到与 boxes[r] 相同颜色的盒子，假设在位置 x 找到这样的盒子，那么将 [x+1, r-1] 这个区间的盒子都移除掉，然后再考虑移除 [l, x] 这个区间的盒子；
  • 那么此时的状态转移方程为：dp[l][r][k] = dp[x+1][r-1][0] + dp[l][x][k+1]。

具体代码实现如下。

代码实现

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        # 定义 dp
        n = len(boxes)
        dp = [[[0] * n for _ in range(n)] for _ in range(n)]

        def cacl_point(boxes, l, r, k):
            """计算积分
            Args:
                boxes: 序列
                l: 序列的起始位置
                r: 序列的结束位置
                k: r 后面与 boxes[r] 相同颜色盒子的个数
            Returns:
                返回序列中策略的最大积分
            """
            if l > r:
                return 0
            
            # 防止重复计算
            if dp[l][r][k] != 0:
                return dp[l][r][k]
            
            # 首先先找与 boxes[r] 相同颜色的盒子
            while l < r and boxes[r] == boxes[r-1] :
                r -= 1
                k += 1
            
            # 策略一（描述见文章）
            dp[l][r][k] = cacl_point(boxes, l, r-1, 0) + (k+1)*(k+1)
            # 策略二（描述见文章）
            for x in range(l, r-1):
                if boxes[x] == boxes[r]:
                    # 这里直接比较出较大值，维护更新
                    dp[l][r][k] = max(dp[l][r][k], cacl_point(boxes, x+1, r-1, 0)+cacl_point(boxes, l, x, k+1))
            return dp[l][r][k]

        return cacl_point(boxes, 0, n-1, 0)

实现结果

欢迎关注

公众号 【书所集录】