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. 代码如下: