给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。 你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 k 个盒子(k >= 1),这样一轮之后你将得到 k*k
个积分。
当你将所有盒子都去掉之后,求你能获得的最大积分和。
示例:
输入: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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-boxes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
dp[i][j][k]
表示区间[i,j]
后面有 k
个连续元素跟 j
下标处相同k+1
个一样的 dp[i][j][k] = dp[i][j-1][0] + (k+1)*(k+1)
p in [i, j-1]
,当b[p]==b[j]
时,消除[p+1,j-1]
区间,dp[i][j][k] = dp[p+1][j-1][0] + dp[i][p][k+1]
class Solution {//显示全过了,但是超时
public:
int removeBoxes(vector<int>& boxes) {
int dp[101][101][101];
memset(dp, 0, sizeof dp);
//dp[i][j][k] 表示区间[i,j]后面有 k 个连续元素跟 j 相同
int n = boxes.size(), i, j, k, p, len;
for(len = 1; len <= n; len++)
{
for(i = 0; i+len-1 < n; ++i)
{
j = i+len-1;
for(k = 0; k < n; ++k)
{
//策略1
//消除右侧的k+1个一样的
dp[i][j][k] = max(dp[i][j][k], (j-1 < i ? 0 : dp[i][j-1][0])+(k+1)*(k+1));
for(p = i; p <= j-1; p++)
{
//策略2, 消除[p+1,j-1]区间,b[p]==b[j]时
if(boxes[p] == boxes[j])
{
dp[i][j][k] = max(dp[i][j][k], (p+1 > j-1 ? 0 : dp[p+1][j-1][0]) + dp[i][p][k+1]);
}
}
}
}
}
return dp[0][n-1][0];
}
};
class Solution { //官方解答代码
public:
int dp[100][100][100];
int removeBoxes(vector<int>& boxes) {
memset(dp, 0, sizeof dp);
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 (dp[l][r][k] != 0) return dp[l][r][k];
while (r > l && boxes[r] == boxes[r - 1]) {
r--;
k++;
}
dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
for (int i = l; i < r; i++) {
if (boxes[i] == boxes[r]) {
dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, l, i, k + 1) + calculatePoints(boxes, i + 1, r - 1, 0));
}
}
return dp[l][r][k];
}
};