大厂程序员坦言：学历高技术差，进体制内才是明智之选

这话有点损，但又挺真实。

大厂里确实有些人，学历看着很能打，简历也漂亮，可真到干活的时候，代码写不利索，方案讲不明白，排查问题全靠旁边人续命。你说他不努力吧，也未必，就是那个赛道不太适合。

但这种人去了体制内，反而可能舒服很多。学历能用上，表达别太拉，流程别出错，材料别写得太离谱，很多时候就已经够用了。技术短板没那么容易暴露，反倒是学校背景、稳定性、听安排这些东西，变成了优势。

所以有时候人菜不一定是人不行，可能是地方没选对。换个环境，可能就成了“综合素质不错”。这事儿最扎心的地方就在这。

今日算法题

移除盒子这题，别急着写二维区间 DP

这题第一眼很像区间 DP， dp[l][r] 表示移除 l~r 的最大分数。 但你真这么写，基本会卡住。

问题出在这条规则上：连续 k 个相同颜色盒子，一次移除得 k*k 分。

比如：

[1, 3, 1]

中间的 3 先删掉，两个 1 就能合并，分数变高。

所以 dp[l][r] 不够，它不知道区间右边还“挂着”几个和 boxes[r] 相同的盒子。这个状态丢了，后面就补不回来。

我一般看到这种“删完之后还能合并”的题，第一反应不是切区间，而是给区间多带一个尾巴。

状态这样定义：

dfs(l, r, k)

表示处理 boxes[l...r] ，并且在 r 的右边，已经有 k 个和 boxes[r] 相同颜色的盒子等着一起删。

这里的 k 很关键。

比如当前右端是颜色 2 ，右边还挂了 3 个 2 ，那最后删右端这一坨的时候，就不是删 1 个，而是删 k+1 个。

先看最直接的选择：把右端这一组删掉。

dfs(l, r-1, 0) + (k+1)*(k+1)

但这还不够。

如果前面某个位置 i 也等于 boxes[r] ，那就可以先把 i+1...r-1 清掉，让 boxes[i] 和 boxes[r] 接上。

这就是这题最别扭的地方。不是马上删，而是忍一下，等它们合并。

状态转移就是：

dfs(l, i, k+1) + dfs(i+1, r-1, 0)

意思是： 中间那段先删掉； 右端这个盒子不单独处理，挂到 i 那边去。

Go 代码我会这么写，别搞太多花活，递归记忆化最清楚：

package main

funcremoveBoxes(boxes []int)int {
n := len(boxes)
if n == 0 {
return0
}

memo := make([][][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([][]int, n)
for j := 0; j < n; j++ {
memo[i][j] = make([]int, n)
}
}

var dfs func(int, int, int)int

dfs = func(l, r, tail int)int {
if l > r {
return0
}

if memo[l][r][tail] != 0 {
return memo[l][r][tail]
}

// 先把右边连续相同的盒子压缩掉
// 这一步不做也能跑，但状态会膨胀，看着就难受
rr := r
kk := tail
for rr > l && boxes[rr] == boxes[rr-1] {
rr--
kk++
}

best := dfs(l, rr-1, 0) + (kk+1)*(kk+1)

for i := l; i < rr; i++ {
if boxes[i] != boxes[rr] {
continue
}

score := dfs(l, i, kk+1) + dfs(i+1, rr-1, 0)
if score > best {
best = score
}
}

memo[l][r][tail] = best
return best
}

return dfs(0, n-1, 0)
}

这里有个小坑，代码里压缩右端连续盒子之后，用的是 rr 和 kk ，但缓存还是写回 memo[l][r][tail] 。

不要顺手写成 memo[l][rr][kk] 。 那样不是不能做，但你后面读缓存时状态就对不上了，容易把自己绕进去。

拿一个例子过一下：

[1, 3, 1]

如果直接删右边的 1 ，收益是：

dfs(0,1,0) + 1

但循环扫到 i=0 ，发现 boxes[0] == boxes[2] ，就会尝试：

dfs(0,0,1) + dfs(1,1,0)

也就是先删中间的 3 ，再把两个 1 合起来删。

这一步就是这题的命门。

这类题不能只盯着“当前怎么删最赚”。 有些盒子现在删是 1 分，留一下，等旁边清干净了，可能就是 4 分、9 分。

所以它看起来是删除题，实际考的是：状态里有没有记录“未来能不能合并”。

dfs(l, r, k) 这个 k ，就是整题最值钱的那个字段。