移除盒子
方法一:动态规划
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)$。