0546. 移除盒子

• 标签：记忆化搜索、数组、动态规划
• 难度：困难

题目链接

• 0546. 移除盒子 - 力扣

题目大意

描述：给定一个代表不同颜色盒子的正数数组 $boxes$，盒子的颜色由不同正数组成，其中 $boxes[i]$ 表示第 $i$ 个盒子的颜色。

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

要求：返回我们能获得的最大积分和。

说明：

• $1 \le boxes.length \le 100$。
• $1 \le boxes[i] \le 100$。

示例：

• 示例 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 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

• 示例 2：

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

解题思路

思路 1：动态规划

对于每个盒子，

如果使用二维状态 $dp[i][j]$ 表示为：移除区间 $[i, j]$ 之间的盒子，所能够得到的最大积分和。但实际上，移除区间 $[i, j]$ 之间盒子，所能得到的最大积分和，并不只依赖于子区间，也依赖于之前移除其他区间对当前区间的影响。比如当前区间的某个值和其他区间的相同值连起来可以获得更高的额分数。

因此，我们需要再二维状态的基础上，增加更多维数的状态。

对于当前区间 $[i, j]$，我们需要凑一些尽可能长的同色盒子一起消除，从而获得更高的分数。我们不妨每次都选择消除区间 $[i, j]$ 中最后一个盒子 $boxes[j]$，并且记录 $boxes[j]$ 之后与 $boxes[j]$ 颜色相同的盒子数量。

1. 划分阶段

按照区间长度进行阶段划分。

2. 定义状态

定义状态 $dp[i][j][k]$ 表示为：移除区间 $[i, j]$ 之间的盒子，并且区间右侧有 $k$ 个与 $boxes[j]$ 颜色相同的盒子，所能够得到的最大积分和。

3. 状态转移方程

• 当区间长度为 $1$ 时，当前区间只有一个盒子，区间末尾有 $k$ 个与 $boxes[j]$ 颜色相同的盒子，所能够得到的最大积分为 $(k + 1) \times (k + 1)$。
• 当区间长度大于 $1$ 时，对于区间末尾的 $k$ 个与 $boxes[j]$ 颜色相同的盒子，有两种处理方式：
  • 将末尾的盒子移除，所能够得到的最大积分为：移除末尾盒子之前能够获得的最大积分和，再加上本轮移除末尾盒子能够获得的积分和，即：$dp[i][j - 1][0] + (k + 1) \times (k + 1)$。
  • 在区间中找到一个位置 $t$，使得第 $t$ 个盒子与第 $j$ 个盒子颜色相同，先将区间 $[t + 1, j - 1]$ 的盒子消除，然后继续凑同色盒子，即：$dp[t + 1][j - 1][0] + dp[i][t][k + 1]$。

4. 初始条件

• 区间长度为 $1$ 时，当前区间只有一个盒子，区间末尾有 $k$ 个与 $boxes[j]$ 颜色相同的盒子，所能够得到的最大积分为 $(k + 1) \times (k + 1)$。

5. 最终结果

根据我们之前定义的状态，$dp[i][j][k]$ 表示为：移除区间 $[i, j]$ 之间的盒子，并且区间右侧有 $k$ 个与 $boxes[j]$ 颜色相同的盒子，所能够得到的最大积分和。所以最终结果为 $dp[0][size - 1][0]$。

思路 1：代码

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        size = len(boxes)

        dp = [[[0 for _ in range(size)] for _ in range(size)] for _ in range(size)]
        for l in range(1, size + 1):
            for i in range(size):
                j = i + l - 1
                if j >= size:
                    break

                for k in range(size - j):
                    if l == 1:
                        dp[i][j][k] = max(dp[i][j][k], (k + 1) * (k + 1))
                    else:
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][0] + (k + 1) * (k + 1))
                    for t in range(i, j):
                        if boxes[t] == boxes[j]:
                            dp[i][j][k] = max(dp[i][j][k], dp[t + 1][j - 1][0] + dp[i][t][k + 1])

        return dp[0][size - 1][0]

思路 1：复杂度分析

• 时间复杂度：$O(n^4)$，其中 $n$ 为数组 $boxes$ 的元素个数。
• 空间复杂度：$O(n^3)$。