1. 题目
读题
链接：https://www.nowcoder.com/questionTerminal/a5390d76441647fbb182f34bee6a1ca7
来源：牛客网
一维消消乐
1、给出一些不同颜色的豆子，豆子的颜色用数字（0-9）表示，即不同的数字表示不同的颜色； 2、通过不断地按行消除相同颜色且连续的豆子来积分，直到所有的豆子都消掉为止； 3、假如每一轮可以消除相同颜色的连续 k 个豆子（k >= 1），这样一轮之后小v将得到 k*k 个积分； 4、由于仅可按行消除，不可跨行或按列消除，因此谓之“一维消消乐”。请你帮助小v计算出最终能获得的最大积分。 这道题 和 leetcode 546. 移除盒子 是同一道原题
考查点
2. 解法
思路
- 定义一个三维数组dp[i][j][k]，表示区间[i,j]内，左边有k个与boxes[j]相同的盒子时的最大积分。
- 动态转移方程是，
dp[i][j][k] = max(calculate(boxes, dp, i, j - 1, 0) + (k + 1) * (k + 1), calculate(boxes, dp, i, m, k + 1) + calculate(boxes, dp, m + 1, j - 1, 0))，其中m是区间[i,j-1]内与boxes[j]相同颜色的盒子的下标。
- 这个方程的意思是，我们可以选择移除最右边的盒子，或者将区间内与最右边盒子相同颜色的盒子移动到右边，然后计算两个子问题的最大积分和。我们需要在这两种选择中取最大值作为当前状态的值。
代码逻辑
- 首先，我们需要定义一个三维数组dp[i][j][k]，表示区间[i,j]内，左边有k个与boxes[j]相同的盒子时的最大积分。
- 然后，我们需要找到状态转移方程，即如何从已知的状态得到未知的状态。
- 一种基本的情况是，我们只移除最右边的盒子，那么我们可以得到dp[i][j][k] = calculate(boxes, dp, i, j - 1, 0) + (k + 1) * (k + 1)，其中calculate是一个递归函数，用来计算子问题的答案。
- 另一种情况是，我们尝试将区间[i,j-1]内与boxes[j]相同颜色的盒子移动到右边，这样可以增加积分。为了找到这样的盒子，我们需要遍历区间[i,j-1]，并且判断是否有boxes[m] == boxes[j]。如果有，那么我们可以将区间[i,j-1]分成两个子区间[i,m]和[m+1,j-1]，并且计算它们的最大积分和。
- 我们需要在这两种情况中选择最大的积分作为dp[i][j][k]的值，并且记录下来，避免重复计算。
- 最后，我们返回dp[0][n-1][0]作为最终答案，其中n是盒子的数量。
具体实现
class Solution {
public int removeBoxes(int[] boxes) {
// dp[i][j][k]表示区间[i,j]内，左边有k个与boxes[j]相同的盒子时的最大积分
int[][][] dp = new int[100][100][100];
return calculate(boxes, dp, 0, boxes.length - 1, 0);
}
public int calculate(int[] boxes, int[][][] dp, int i, int j, int k) {
if (i > j) return 0; // 空区间
if (dp[i][j][k] != 0) return dp[i][j][k]; // 已经计算过
// 优化：合并右边连续相同颜色的盒子
while (i < j && boxes[j] == boxes[j - 1]) {
j--;
k++;
}
// 基本情况：只移除最右边的盒子
dp[i][j][k] = calculate(boxes, dp, i, j - 1, 0) + (k + 1) * (k + 1);
// 尝试将区间[i,j-1]内与boxes[j]相同颜色的盒子移动到右边
for (int m = i; m < j; m++) {
if (boxes[m] == boxes[j]) {
// 计算两个子区间的最大积分和
dp[i][j][k] = Math.max(dp[i][j][k], calculate(boxes, dp, i, m, k + 1) + calculate(boxes, dp, m + 1, j - 1, 0));
}
}
return dp[i][j][k];
}
}