0546：移除盒子（★★）

力扣第 546 题

题目

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

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 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 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)

示例 2：

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

示例 3：

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

提示：

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

分析

显然初始连续的盒子最后是一起移除的，考虑将连续段合并，得到元素为 (颜色，连续段长度) 的数组 A。

• 考虑元素 A[-1]，它要么单独移除，要么和前面颜色相同的元素一起移除
• 假如 A[-1] 单独移除，显然转为递归子问题
• 假如 A[-1] 和 A[i] 一起移除
  • 必然先移除了 A[i+1:-1] 部分，这部分即是子问题
  • 然后将 A[-1] 的长度累加到 A[i] 上，剩下的也是子问题

因此令 dfs(A) 代表数组 A 的最大积分，即可递归。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def removeBoxes(self, boxes: List[int]) -> int:
    @lru_cache(None)
    def dfs(A):
        if not A:
            return 0
        c, k = A[-1]
        res = dfs(A[:-1])+k**2
        for i in range(len(A)-2):
            if A[i][0]==c:
                B = A[:i]+((c, A[i][1]+k),)
                res = max(res, dfs(B)+dfs(A[i+1:-1]))
        return res

    A = tuple((x, len(list(g))) for x, g in groupby(boxes))
    return dfs(A)

364 ms

*附加

时间复杂度分析：

• 注意到递归时只会对区间数组的末尾进行修改，因此可以改写成一般的区间 dp 形式
  • 令 dfs(i, j, k) 代表 A[i:j+1] 且 A[j] 额外加了 k 的最大积分，即可递归
  • 显然 k 小于 n，因此一般的区间 dp 写法的时间复杂度是 O(N^4)
• 直接递归区间数组的形式，有切片操作，所以时间复杂度更高
• 但因为本题的数值范围很小，一般会存在重复的区间数组，所以直接递归区间数组的实际时间更快