跳转至

546. 移除盒子

题目描述

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

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

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

 

示例 1：

输入：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：

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

示例 3：

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

 

提示：

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

解法

方法一：记忆化搜索

设计递归函数 dfs(i, j, k) 表示当前处理的区间为 [i, j]，且该区间的右边有 k 个与 boxes[j] 相同的元素，返回该区间的最大积分。答案即为 dfs(0, n - 1, 0)。

对于 dfs(i, j, k)，我们可以直接删除 boxes[j] 和其右边的 k 个元素，所得积分为 dfs(i, j - 1, 0) + (k + 1) * (k + 1)。

我们还可以在区间 [i, j-1] 内枚举下标 h，找到满足 boxes[h] == boxes[j] 的下标，那么我们就将区间 [i, j - 1] 分成两部分，即 [i, h] 和 [h + 1, j - 1]。其中 [i, h] 的部分可以与 boxes[j] 合并，所以积分为 dfs(i, h, k + 1) + dfs(h + 1, j - 1, 0)。求不同 h 下的最大值即可。

我们使用记忆化搜索来优化递归函数的时间复杂度。

时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dfs(i, j, k):
            if i > j:
                return 0
            while i < j and boxes[j] == boxes[j - 1]:
                j, k = j - 1, k + 1
            ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1)
            for h in range(i, j):
                if boxes[h] == boxes[j]:
                    ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1))
            return ans

        n = len(boxes)
        ans = dfs(0, n - 1, 0)
        dfs.cache_clear()
        return ans

 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
class Solution {
    private int[][][] f;
    private int[] b;

    public int removeBoxes(int[] boxes) {
        b = boxes;
        int n = b.length;
        f = new int[n][n][n];
        return dfs(0, n - 1, 0);
    }

    private int dfs(int i, int j, int k) {
        if (i > j) {
            return 0;
        }
        while (i < j && b[j] == b[j - 1]) {
            --j;
            ++k;
        }
        if (f[i][j][k] > 0) {
            return f[i][j][k];
        }
        int ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1);
        for (int h = i; h < j; ++h) {
            if (b[h] == b[j]) {
                ans = Math.max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1));
            }
        }
        f[i][j][k] = ans;
        return ans;
    }
}

 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
class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(n)));
        function<int(int, int, int)> dfs;
        dfs = [&](int i, int j, int k) {
            if (i > j) return 0;
            while (i < j && boxes[j] == boxes[j - 1]) {
                --j;
                ++k;
            }
            if (f[i][j][k]) return f[i][j][k];
            int ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1);
            for (int h = i; h < j; ++h) {
                if (boxes[h] == boxes[j]) {
                    ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1));
                }
            }
            f[i][j][k] = ans;
            return ans;
        };
        return dfs(0, n - 1, 0);
    }
};

 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
func removeBoxes(boxes []int) int {
    n := len(boxes)
    f := make([][][]int, n)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, n)
        }
    }
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i > j {
            return 0
        }
        for i < j && boxes[j] == boxes[j-1] {
            j, k = j-1, k+1
        }
        if f[i][j][k] > 0 {
            return f[i][j][k]
        }
        ans := dfs(i, j-1, 0) + (k+1)*(k+1)
        for h := i; h < j; h++ {
            if boxes[h] == boxes[j] {
                ans = max(ans, dfs(h+1, j-1, 0)+dfs(i, h, k+1))
            }
        }
        f[i][j][k] = ans
        return ans
    }
    return dfs(0, n-1, 0)
}

评论