0546：移除盒子（★★）

2016-06-29 约 529 字预计阅读 2 分钟次阅读

力扣第 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

相似问题：

分析

#1

考虑最后一个盒子，只有两种情况
- 单独移除
- 和前面的某个 boxes[k] 一起移除
  - 必然先移除了 [k+1:-1] 部分，转为递归子问题
  - 然后将 boxes[-1] 加到 boxes[k] 后面，转为递归子问题
为了方便递归，令 dfs(i,j,x) 代表区间 [i,j] 且跟了 x 个 boxes[j] 的最大得分

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


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dfs(i,j,x):
            if i>j:
                return 0
            res = (x+1)*(x+1)+dfs(i,j-1,0)
            for k in range(i,j):
                if boxes[k]==boxes[j]:
                    res = max(res,dfs(i,k,x+1)+dfs(k+1,j-1,0))
            return res
        n = len(boxes)
        return dfs(0,n-1,0)

4595 ms

#2

显然初始连续的盒子应该一起移除
考虑将连续段合并，得到元素为 (颜色，连续段长度) 的数组 A
在数组 A 上进行递归，可以节省时间

解答

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


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dfs(i,j,x):
            if i>j:
                return 0
            x += A[j][1]
            res = x*x+dfs(i,j-1,0)
            for k in range(i,j):
                if A[k][0]==A[j][0]:
                    res = max(res,dfs(i,k,x)+dfs(k+1,j-1,0))
            return res

        A = [(c,len(list(g))) for c,g in groupby(boxes)]
        n = len(A)
        return dfs(0,n-1,0)

576 ms

目录

0546：移除盒子（★★）

题目

分析

#1

#2

解答