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)

实现后果

欢送关注

公众号【书所集录】