[LeetCode]546. 移除盒子(Remove Boxes)

一道较难的动态规划题目,同时也是 2019 年 VIVO 的笔试真题。

题目描述

给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 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。

解题思路

动态规划。设置三状态 DP 数组 dp[i][j][k] 表示闭区间 [i, j] 且该区间右边有 k 个盒子与右边界 nums[j] 相等时,消去所得的最大积分和。即我们最终要求 dp[0][n - 1][0]
对于 dp[i][j][k],我们有两种消去方案:

  1. 消去 j 以及之后的 k 个盒子共 k + 1 个,可得的最终积分和为 dp[i][j - 1][0] + (k + 1)^2
  2. 实际上若区间内部有与右边界 nums[j] 相同的盒子 idx,那么应该先消去 [idx + 1, j - 1] 这段,因为这可以使得第 idx 个盒子与相同的第 j 个盒子相邻起来,能够获得更大的收益。这样将子串分为了两部分:

    1. dp[idx + 1][j - 1][0]
    2. dp[i][idx][k + 1]。消去第一部分之后,原本不相邻的相等元素相邻了。

      最终将这两部分加起来即可。

最终对这两部分取最大的即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def removeBoxes(self, boxes: List[int]) -> int:
length = len(boxes)
dp = [[[0] * length for _ in range(length)] for _ in range(length)]
return self.dp_i_j_k(boxes, dp, 0, length - 1, 0)

def dp_i_j_k(self, boxes, dp, i, j, k):
if i > j:
return 0
if dp[i][j][k] > 0:
return dp[i][j][k]
while i < j and boxes[j] == boxes[j - 1]:
j -= 1
k += 1
dp[i][j][k] = self.dp_i_j_k(boxes, dp, i, j - 1, 0) + (k + 1) ** 2
for idx in range(i, j):
if boxes[idx] == boxes[j]:
dp[i][j][k] = max(dp[i][j][k], self.dp_i_j_k(boxes, dp, i, idx, k + 1) + self.dp_i_j_k(boxes, dp, idx + 1, j - 1, 0))
return dp[i][j][k]

执行用时 : 308 ms
内存消耗 : 22.3 MB

参考

https://blog.csdn.net/u014626513/article/details/81227574