Keshawn_lu's Blog

Leetcode 546. 移除盒子

动态规划 深度优先搜索
字数统计: 610阅读时长: 2 min
2020/08/15 Share

题目简介：

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。

当你将所有盒子都去掉之后，求你能获得的最大积分和。

示例：

1
2
3
4
5
6
7
8
输入：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 分)

提示：

  • 1 <= boxes.length <= 100
  • 1 <= boxes[i] <= 100

思路：

三维的动态规划，dp[left][right][num]代表移除[left, right]区间 和 [right + 1, maxsize]区间内num个与boxes[right]相等的元素，所能达到的最大积分。

那么我们在移除元素时也有两种策略，就和玩祖玛游戏一样，有序列112231111：

  1. 先把后面的四个1移除，那么就是1123 + 4 * 4
  2. 把中间碍事的先给去除，那么就是 22 + 3 + 6 * 6(6个1)

所以对于dp[left][right][num]，我们有两种策略：

  1. 先将right后的num个元素去除，那么就是dp[left][right - 1][0] + (num + 1) * (num + 1)。(把boxes[right]也去除了)
  2. 在[left, right]区间内先找到一个点boxes[i] == boxes[right]，那么dp[left][right][num] = dp[left][i][num + 1] + dp[i + 1][right - 1][0]。(循环找到不止一个点，取最大值)

最后dp[left][right][num]取两者最大值即可。

tips:

  • 若dp[left][right][num]在之前已经计算出来，则直接返回结果即可。
  • 否则利用深度优先搜索将其值计算出来。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:

    int dp[100][100][100] = {0};

    int dfs(vector<int>& boxes, int left, int right, int num){

        if(left > right)
            return 0;

        if(dp[left][right][num] != 0)
            return dp[left][right][num];
        
        while(left < right && boxes[right] == boxes[right - 1]){

            right--;
            num++;
        }

        //决策1
        dp[left][right][num] = dfs(boxes, left, right - 1, 0) + (num + 1) * (num + 1);

        for(int i = left; i < right; i++){

            if(boxes[i] == boxes[right]){

                //决策2
                int sum = dfs(boxes, left, i, num + 1) + dfs(boxes, i + 1, right - 1, 0);
                dp[left][right][num] = max(dp[left][right][num], sum);
            }
        }

        return dp[left][right][num];
    }

    int removeBoxes(vector<int>& boxes) {

        return dfs(boxes, 0, boxes.size() - 1, 0);
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网