题面
给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。 当你将所有盒子都去掉之后，求你能获得的最大积分和。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-boxes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
用f[l][r]来表示移除区间 [l,r] 内所有的盒子能得到的最大积分，然后去探索某一种移除盒子的策略来进行状态转移,这个方法应该是大部分人的第一个想法,官方题解称之错误的思路,但实际上,它是可以做出来的,只是状态转移方程比较特殊.
首先枚举的是[i,j]区间,对于确定的区间,如何确定f[i][j]呢,我是枚举最后一次消除的是哪个数(以后用numx代替),比如样例[1,3,2,2,2,3,4,3,1],
i=0,j=2,[1,3]最后一个可以是1或3
i=0,j=8,[1,3,2,2,2,3,4,3,1],最后一个可以是1,3,2或者4
我们知道最后的消除的是谁了,那么,一个朴素的想法,$(a+b)^2>a^2+b^2$,把所有的合一起消掉肯定比分两波甚至更多波好,那么状态转移方程就是
$ f[i][j] = \sum_{(x,y)}f[x][y]+cntx^2$
其中(x,y)是被numx分割的子序列,cntx是numx的个数
聪明的你可能发现了有点不对劲,没错,当我信心满满的交上时,结果WA了
我又仔细想了想,发现加入我们枚举7的时候,有一个子段XXOO,2,2,2,7,2,2,2,XXOO,我们为了7最优,却忽略了被7分开的2,我们放弃这个7去成就2全局可能更好.情况可能更复杂XXOO,2,2,2,7,3,7,4,2,2,2,XXOO,这次要放弃7,3,7,4成就2,也就是说只看7两边一样的数也不行,要看全局!
看全局,怎么看?枚举7的时候有m个7分布在数列不同位置,如果一个个枚举7选不选(在最后一波一起消除),$2^m$太爆炸了,但是,仔细想想,这不是动态规划问题吗(没错,用动态规划维护上面的动态规划的状态转移,套娃警告)
- $g[cnt][num]$表示前cnt个numx,一共num个不参与最后一轮(且第cnt个必定不参与)消除的情况下的最优解
- 初值$g[0][0]=0$
- 状态转移方程: $g[cnt][num] = \max_{0<=per<cnt}(g[per][num-1]+f[posx[per]+1][posx[cnt]-1]))$,其中posx[i]表示第i个numx下标
最后,终于可以更新 $f$ 了
$f[i][j] = max(f[i][j], g[cntx][num]+num*num)$ (1<=num<=cntx)
$f[i][j] = max(f[i][j], g[cnt][num]+num*num+f[posx[cnt]+1][j])$ (1<cnt<cntx,1<=num<=cnt别忘了考虑最后一个numx不参与的情况)
最后:
递推和记忆化搜索本质是相同的,递推写法注意,第一层必须枚举区间长度,先算小区间再算大区间,不要枚举起点终点
$g[cnt][num]$为什么规定第cnt个必定不参与,感觉是经典问题了,为了方便状态转移,必须知道最后一个不参与的是谁,用$g[cnt][num][last]$表示前cnt个numx,一共num个不参与,位置最靠后的不参与的是last的情况下的最优解,优化一下的产物
类似11111211枚举1时显然要把1一次性合并,没必要dp了,我稍微判断了一下$other * other-other <= cntx * cntx-(cntx-1)*(cntx-1))$时,没必要继续dp,算是常数优化吧,当然,可以更精细
我看了官方题解,状态定义非常新颖,转移决策更自然,f(l,r,k)真的很难想到,非常厉害,我的方法虽然慢,但是说明f[i][j]的做法是可行的,还是有点价值的
inline int max(int a,int b){return a>b?a:b;}
int removeBoxes(int* boxes, int boxesSize){
int f[boxesSize+2][boxesSize+2];//f[i][j]表示i到j区间最优解
int g[boxesSize+2][boxesSize+2],posx[boxesSize+2];
int flags[boxesSize+2];
for (int i = 0; i <= boxesSize; i++)
for (int j = 0; j <= boxesSize; j++)
f[i][j] = 0;
for (int i = 0; i < boxesSize; i++) {
flags[i] = 0;
f[i][i] = 1;
}
for (int len = 2; len <= boxesSize; len++) //枚举区间长度
for (int i = 0; i+len-1 < boxesSize; i++) { //枚举起点
int j = i+len-1; //区间i到j
int flag = i*10000+j; //一个特殊标记flag判重,防止枚举重复数字
for (int x = i; x <= j; x++) //枚举这个区间最后消除的数字numx
if (flags[x] != flag) {
flags[x] = flag;
int tmp = x?f[i][x-1]:0; //tmp记录numx分割开的子区间最优解的和
int cntx = 1,lastx = x; //cntx为numx的数量,lastx是邻近的前一个numx的下标
posx[0] = i-1; //posx[i]记录第i个numx下标
posx[1] = x;
for (int k = x+1; k <= j; k++) {
if (boxes[k] == boxes[x]) {
cntx++;
posx[cntx] = k;
tmp += f[lastx+1][k-1];
lastx = k;
flags[k] = flag;
} else {
if (k == j)
tmp += f[lastx+1][j];
}
}
tmp += cntx*cntx; //加上最后消除numx的得分(此处只考虑所有numx都在最后消除)
if (tmp > f[i][j])
f[i][j] = tmp;
int other = len-cntx;
if (cntx==1 || other*other-other <= cntx*cntx-(cntx-1)*(cntx-1))
continue; //优化,极端情况(把所有other集合起来利益不如numx缺少一个的损失)不需要下面计算
for (int cnt = 0; cnt <= cntx; cnt++)
for (int num = 0; num <= cntx; num++)
g[cnt][num] = -233333;
g[0][0] = 0; //初始化
//g[i][j]表示前i个numx,一共j个不参与最后一轮(且第i个不参与)的情况下的最优解
for (int cnt = 1; cnt <= cntx; cnt++) //考虑前cnt个numx
for (int num = 1; num <= cnt; num++) //枚举不参与最后一轮的numx的个数
for (int per = 0; per < cnt; per++) { //枚举前驱 -- 上一个不参与的numx是谁
if (posx[cnt] > 0)
g[cnt][num] = max(g[cnt][num], g[per][num-1]+f[posx[per]+1][posx[cnt]-1]);
else
g[cnt][num] = max(g[cnt][num], g[per][num-1]);
}
for (int num = 1; num <= cntx; num++)
f[i][j] = max(f[i][j], g[cntx][num]+num*num); //更新答案
for (int cnt = 1; cnt < cntx; cnt++)
for (int num = 1; num <= cnt; num++)
f[i][j] = max(f[i][j], g[cnt][num]+num*num+f[posx[cnt]+1][j]);
//考虑最后一个numx不参与的情况
}
}
return f[0][boxesSize-1];
}
作者：wineee
链接：https://leetcode-cn.com/problems/remove-boxes/solution/zhen-zheng-de-fang-fa-er-yong-flr-lai-biao-shi-yi-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间复杂度：$O(n^5)$,比官方题解高,因为常数比较小,实际表现不算太差,击败6.25% 的用户已经很好了。注意不要数for循环,比如x*cnt的两个循环只能算$O(n)$
空间复杂度：$O(n^2)$,击败100.00% 的用户无压力