移除盒子

Category Difficulty Likes Dislikes
algorithms Hard (62.04%) 366 -
Tags

dynamic-programming | depth-first-search

Companies

Unknown

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

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

返回 你能获得的最大积分和 。

示例 1：

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 分)

示例 2：

1
2
输入：boxes = [1,1,1]
输出：9

示例 3：

1
2
输入：boxes = [1]
输出：1

动态规划 + 递归(c++)

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
41
42
43
44
/*
 * @lc app=leetcode.cn id=546 lang=cpp
 *
 * [546] 移除盒子
 */

/** 
 * f[l, r, k] = max(f[l, r-1, 0] + (k + 1)²)
 * 
 * 6365676686
 * f[0,0,0] = 
 */

// @lc code=start
class Solution {
public:
    int f[100][100][100];
    int removeBoxes(vector<int>& boxes) {
        memset(f, 0, sizeof f);
        return calculatePoints(boxes, 0, boxes.size() - 1, 0);
    }
    int calculatePoints(vector<int>& boxes, int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (f[l][r][k] == 0) {
            int k1 = k, r1 = r;
            while (r1 > l && boxes[r1] == boxes[r1 - 1]) {
                --r1;
                ++k1;
            }
            f[l][r][k] = calculatePoints(boxes, l, r1 - 1, 0) + (k1 + 1) * (k1 + 1);
            for (int i = l; i < r1; ++i) {
                if (boxes[i] == boxes[r]) {
                    f[l][r][k] = max(f[l][r][k], calculatePoints(boxes, l, i, k1 + 1) + calculatePoints(boxes, i + 1, r1 - 1, 0));
                }
            }
        }
        return f[l][r][k];
    }
};
// @lc code=end