一道较难的动态规划题目,同时也是 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]
,我们有两种消去方案:
- 消去
j
以及之后的k
个盒子共k + 1
个,可得的最终积分和为dp[i][j - 1][0] + (k + 1)^2
; 实际上若区间内部有与右边界
nums[j]
相同的盒子idx
,那么应该先消去[idx + 1, j - 1]
这段,因为这可以使得第idx
个盒子与相同的第j
个盒子相邻起来,能够获得更大的收益。这样将子串分为了两部分:dp[idx + 1][j - 1][0]
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
19class 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