跳转至

LeetCode: 546. 移除盒子

1、题目描述

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

示例 1:

输入:

[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 分)

**提示:**盒子的总数 n 不会超过 100

2、解题思路

  • 使用暴力法肯定会超时的,实际上,我们每一次都会将其中的一部分移除,然后不同的移除方案可能得到相同的数组,因此这些数组所得到的结果应该是相同的

  • 使用dfs+记忆化

l,r,k

左下标,右下标,右下标之后还有k个右下标对应数字相等的连续值

初始状态,l=0,r=length-1,k=0

然后从右向左找出连续的值,找到第一个不同的位置,这时候可以选择将最右方的进行移除,得到一组结果

如果将中间的结果进行移除,有可能会将右方的数字连成更长的一组数,然后就需要考虑这种情况

在l,r中间开始查找,确认有没有与右方数字相同的,如果没有,这时候直接移除右方的数字肯定是最大的情况
如果存在,就需要对这种情况进行更新,
ans = max(ans, dfs(l, i, k + 1) + dfs(i + 1, r - 1, 0))

上面的就是先移除 [i + 1, r - 1] 范围的数字,然后会得到更多的连续值,因此在i之后,还有k+1个数字与右方的相同,然后重复上面的步骤
from functools import lru_cache


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

        @lru_cache(None)
        def dfs(l, r, k):
            if r < l:
                return 0
            while r > l and boxes[r] == boxes[r - 1]:
                r -= 1
                k += 1
            ans = dfs(l, r - 1, 0) + (k + 1) ** 2
            for i in range(l, r):
                if boxes[i] == boxes[r]:
                    ans = max(ans, dfs(l, i, k + 1) + dfs(i + 1, r - 1, 0))
            return ans

        return dfs(0, len(boxes) - 1, 0)