0%

leetcode每日一题-移除盒子

Posted on In ,

移除盒子

image1

方法一：动态规划

1
一次可以移除具有相同颜色的连续盒子，是每次只能移除一个滑窗，而不是一次移除同一种颜色所有地方
2
* 设dp[l][r][k]
3
  起始下标l(以0开始)，结束下标r，k表示在下标r后面紧接着有k个元素值和boxes[r]相同，的最大积分和
4
* 比如[l,l+1,···,r-1,r,值同r，值同r，值同r]
5
  这里有3个元素和boxes[r]相同，即k==3，那么dp[l][r][3]=dp[l][r-1][0]+4*4
6
  因为有3个和[r]相同，即可以消除4个所以加上4*4
7
** 得到初始化条件dp[l][r][k]=dp[l][r-1][0]+(k+1)*(k+1)
8
* 但是有可能在boxes[l]~boxes[r-1]中也存在和boxes[r]相同值的元素，有可能获得更大的积分和
9
  比如[l,l+1,···,i,···,r-1,r,值同r，值同r，值同r]，假设boxes[i]==boxes[r]
10
  那么可能先移除boxes[i+1]~boxes[r-1]，这样就能使原来的dp[l][r][3]的k=3变的更大，但是r变得更小，但是积分和更大
11
  因此就需要在boxes[l]~boxes[r-1]中找到boxes[i]==boxes[r]
12
** 这样子先移除boxes[i+1]~boxes[r-1]，这一部分的最大积分和是dp[i+1][r-1][0]
13
  移除之后是[l,l+1,···,i,值同i(原来是r)，值同i(原来是r+1)，值同i(原来是r+2)，值同i(原来是r+3)]
14
  剩下这部分是dp[l][i][k+1]
15
** 总和起来就是dp[l][r][k]=max(dp[l][r][k],dp[i+1][r-1][0]+dp[l][i][k+1])
16
* 最后的答案就是dp[0][boxes.size()-1][0]

一次可以移除具有相同颜色的连续盒子，是每次只能移除一个滑窗，而不是一次移除同一种颜色所有地方。

设dp[l][r][k]起始下标l(以0开始)，结束下标r，k表示在下标r后面紧接着有k个元素值和boxes[r]相同的最大积分和。比如[l,l+1,···,r-1,r,值同r，值同r，值同r]这里有3个元素和boxes[r]相同，即k==3，那么dp[l][r][3]=dp[l][r-1][0]+4*4因为有3个和[r]相同，即可以消除4个所以加上4*4。

得到初始化条件dp[l][r][k]=dp[l][r-1][0]+(k+1)*(k+1)

  • 但是有可能在boxes[l]~boxes[r-1]中也存在和boxes[r]相同值的元素，有可能获得更大的积分和
    比如[l,l+1,···,i,···,r-1,r,值同r，值同r，值同r]，假设boxes[i]==boxes[r]
    那么可能先移除boxes[i+1]~boxes[r-1]，这样就能使原来的dp[l][r][3]的k=3变的更大，但是r变得更小，但是积分和更大。因此就需要在boxes[l]~boxes[r-1]中找到boxes[i]==boxes[r]，这样子先移除boxes[i+1]~boxes[r-1]，这一部分的最大积分和是dp[i+1][r-1][0]移除之后是[l,l+1,···,i,值同i(原来是r)，值同i(原来是r+1)，值同i(原来是r+2)，值同i(原来是r+3)]，剩下这部分是dp[l][i][k+1]，总和起来就是dp[l][r][k]=max(dp[l][r][k],dp[i+1][r-1][0]+dp[l][i][k+1])。
  • 最后的答案就是dp[0][boxes.size()-1][0]
1
class Solution {
2
    public int removeBoxes(int[] boxes) {
3
        int[][][] dp = new int[100][100][100];
4
        return calculatePoints(boxes, dp, 0, boxes.length - 1, 0);
5
    }
6
7
    public int calculatePoints(int[] boxes, int[][][] dp, int l, int r, int k) {
8
        if (l > r) return 0;
9
        if (dp[l][r][k] != 0) return dp[l][r][k];
10
        while (r > l && boxes[r] == boxes[r - 1]) {
11
            r--;
12
            k++;
13
        }
14
        dp[l][r][k] = calculatePoints(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
15
        for (int i = l; i < r; i++) {
16
            if (boxes[i] == boxes[r]) {
17
                dp[l][r][k] = Math.max(dp[l][r][k], calculatePoints(boxes, dp, l, i, k + 1) + calculatePoints(boxes, dp, i + 1, r - 1, 0));
18
            }
19
        }
20
        return dp[l][r][k];
21
    }
22
}

复杂度分析：

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