Sui Xin's Blog

[LeetCode]546. 移除盒子（Remove Boxes）

Posted on In , Disqus:

一道较难的动态规划题目，同时也是 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

Related Posts