题目描述
给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 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 分)
输入:boxes = [1,1,1]
输出:9
输入:boxes = [1]
输出:1
限制
1 <= boxes.length <= 100
1 <= boxes[i] <= 100
算法
(区间动态规划) $O(n^4)$
- 此题为另一道区间动态规划题的加强版。基础版的问题为:最少需要多少次操作(操作的规则一样)能删除掉所有的盒子。
- 设 $f(i, j, k)$ 表示删除区间
[i, j]
时,与boxes[i]
一次删除的盒子有 $k$ 个的最大积分。$g(i, j)$ 为删除区间[i, j]
的最大积分,即所有 $f(i, j, k)$ 的最大值。 - 初始时,$f(i, i, 1) = g(i, i) = 1$,其余为负无穷。有个特殊情况是 $[i, i - 1]$ 这个区间在转移时会被用到,应该初始化为 $0$。
- 转移时,我们定义两种情况:(1)
boxes[i]
自己单独删除。(2)boxes[i]
与后边的同颜色的盒子合并删除。 - 对于情况 (1),转移 $f(i, j, 1) = 1 + g(i + 1, j)$。
- 对于情况 (2),转移 $f(i, j, k) = \max(f(i, j, k), g(i + 1, p - 1) + f(p, j, k - 1) - (k - 1)^2 + k^2)$,其中
boxes[i] == boxes[p]
。也就是说,我们找到了盒子boxes[p]
,想要boxes[i]
与它一起删除,则此时的删除操作可以分为两部分,首先删除区间[i + 1, p - 1]
,然后删除盒子i
和区间[p, j]
。由于有了k
这一维,所以假设区间[p, j]
删除时的k - 1
这个信息已经算好了,则区间[i, j]
的k
就可以转移了。 - 最终答案为 $g(i, j)$。
时间复杂度
- 状态数为 $O(n^3)$,转移时间为 $O(n)$,故总时间复杂度为 $O(n^4)$。
空间复杂度
- 需要额外的 $O(n^3)$ 的空间记录状态。
C++ 代码
class Solution {
public:
int removeBoxes(vector<int>& boxes) {
const int MIN = -100000;
int n = boxes.size();
vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(n + 1, MIN)));
vector<vector<int>> g(n, vector<int>(n, MIN));
for (int i = 0; i < n; i++) {
f[i][i][1] = 1;
g[i][i] = 1;
if (i > 0) g[i][i - 1] = 0;
}
for (int len = 2; len <= n; len++)
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
f[i][j][1] = 1 + g[i + 1][j];
for (int p = i + 1; p <= j; p++)
if (boxes[i] == boxes[p])
for (int k = 2; k <= len; k++)
f[i][j][k] = max(f[i][j][k],
g[i + 1][p - 1] + f[p][j][k - 1]
- (k - 1) * (k - 1) + k * k);
for (int k = 1; k <= len; k++)
g[i][j] = max(g[i][j], f[i][j][k]);
}
return g[0][n - 1];
}
};
请问一下基础版问题也是同样的定义状态方式吗?有更简单的办法吗?
不需要,$f(i, j)$ 表示区间 $[i, j]$ 完全消除且最后一次消除的颜色是 $a(i)$ 的最少次数。
谢谢啊,所以是枚举i到j之间的数,
A[k] == A[i]时,$f(i, j) = min_{k}(f(i, k) + f(k + 1, j) - 1)$
其他时候 $f(i, j) = min_{k}(f(i, k) + f(k + 1, j)) 这样子吗。最后输出是$f(1, n)$,这样的话能保证一定是最后消除$a(0)$是最优的吗?
其实最优解都可以转化到最后消除 $a(0)$
哦哦,谢谢,大概理解了,我上面写的转移方程是对的吗?
可以试下,应该没错
f[p][j][k - 1] - (k - 1) * (k - 1) + k * k),为什么不是f[p][j][k - 1] + (k - 1) * (k - 1)
需要去掉 $f(p, j, k - 1)$ 时的得分 $(k - 1)^2$,然后统一算上这次的得分 $k^2$。因为 $boxes(i)$ 需要和之后的盒子一起合并删除
f(i,i,1)=g(i,i)=1 其余为负无穷
这里好像笔误了已修正