35岁被公司裁了，但拿到了40万赔偿金，失业在家4个月，突然看到丈母娘给媳妇儿的信息，人要崩溃了。网友：丈母娘太坏了！

35岁被公司裁了，拿了40万赔偿金，听着好像还能缓一缓。失业在家4个月，也不算离谱吧，谁中年被优化了不得先喘口气，简历投出去也不是当天就有回音。

结果他无意间看到丈母娘给媳妇儿发消息，大概意思就是：别让他在家待太久，赔偿金得看紧点，男人没工作久了靠不住，实在不行要多给自己留后路。

这话看着是真扎心。

你说她完全没担心，也不现实。女儿过日子，有孩子有房贷，她焦虑可以懂。但问题是这个表达，像直接把女婿当风险资产了。前脚刚被公司裁，后脚又被家里贴上“不稳定”标签，谁顶得住啊。

公司算账，家庭也开始算账。人到35岁，最怕的不是没工作，是你一停下来，身边人看你的眼神都变了。

移除盒子这题，别一上来就写贪心。

看到连续相同颜色得分是 k * k，第一反应很容易是：先把眼前能消的最长一段消掉。这个判断不太靠谱。

比如中间隔着一段别的颜色，先把中间那段清掉，两边相同颜色就能合并，分数可能直接翻倍。这个题真正麻烦的地方不是“删哪一段”，而是“能不能留着等后面合并”。

我一般会把它往区间 DP 上靠。

普通区间 DP 写成：

dp[l][r] = 移除 boxes[l...r] 的最大分数

不够。

因为 boxes[r] 右边可能还跟着几个同色盒子，它们已经被前面的递归“攒”出来了。这个数量会影响当前删除得分。

所以状态要多带一个参数：

dfs(l, r, k)

含义是：处理 boxes[l...r]，并且右侧已经有 k 个和 boxes[r] 同色的盒子等着一起删。

这个 k 很关键，少了它，这题基本就写歪了。

先看代码：

classSolution{
privateint[] a;
privateint[][][] cache;

publicintremoveBoxes(int[] boxes){
this.a = boxes;
int n = boxes.length;
this.cache = newint[n][n][n];
return score(0, n - 1, 0);
    }

privateintscore(int left, int right, int sameRight){
if (left > right) {
return0;
        }

if (cache[left][right][sameRight] != 0) {
return cache[left][right][sameRight];
        }

int r = right;
int carry = sameRight;

while (r > left && a[r] == a[r - 1]) {
            r--;
            carry++;
        }

int best = score(left, r - 1, 0) + (carry + 1) * (carry + 1);

for (int mid = left; mid < r; mid++) {
if (a[mid] != a[r]) {
continue;
            }

int keepRightColor = score(left, mid, carry + 1);
int clearMiddle = score(mid + 1, r - 1, 0);

            best = Math.max(best, keepRightColor + clearMiddle);
        }

        cache[left][right][sameRight] = best;
return best;
    }
}

这段代码里最别扭的地方，其实是这个循环：

while (r > left && a[r] == a[r - 1]) {
    r--;
    carry++;
}

它不是优化那么简单。

它是在把右边已经连续的同色盒子先收拢起来。比如最后是：

3, 3, 3

那就别傻乎乎一层层递归了，直接当成右边带了多个 3。这样状态会少很多，递归也干净。

接下来有两个选择。

第一个选择，直接删掉右侧这一坨：

score(left, r - 1, 0) + (carry + 1) * (carry + 1)

这个很好理解。

第二个选择就有点绕：在左边找一个和 a[r] 一样颜色的位置 mid。

if (a[mid] == a[r])

如果中间 mid + 1...r - 1 这段先删掉，那么 a[mid] 就可以和右边的 a[r] 合并。

所以写成：

score(left, mid, carry + 1)
+ score(mid + 1, r - 1, 0)

这里我第一次写的时候也容易反过来，觉得应该先算左边，再算中间。其实递归表达的是最终得分，不是真实执行顺序。关键是：中间清掉以后，左右同色能接上。

这题最坑的点就在这里。

不是每次遇到相同颜色就立刻消，而是有时候要忍一下，等它们凑成更大的一坨。

复杂度看起来是三维状态，再套一层枚举，大概 O(n^4) 的味道。不过题目数据规模不大，加上连续同色压缩，Java 正常能过。

这个题别背模板，记住一句就行：区间里某个颜色将来能不能合并，不能只看 l 和 r，还得把外面“攒着的同色数量”塞进状态里。dfs(l, r, k) 这个 k，就是整题的开关。