1. 题目本质与核心解题思路1.1 原题描述与样例跑一遍UVA 10559 Blocks老牌题目俗称“方块消除”在算法竞赛圈子里的地位几乎等同于区间 DP 的入门必修课。题目本身并不花哨给一行方块每个方块有颜色你每次可以选一段连续且颜色相同的方块消掉得到的分数是该段长度的平方。消完之后左右两边原本不相邻的方块会拼到一起相当于一个简化版的祖玛或消消乐。问整行方块最多能拿多少分。先看一个小例子。假设有 5 个方块颜色依次是 1 2 1 1 2。如果贪心地先把中间的 1 1 消掉得分 4剩下的颜色变成 1 2 2再消 2 2 得 4最后消 1 得 1总分 9。但是如果先处理右边的 2 2得 4 分剩下 1 2 1 1再把 1 1 消掉得 4剩下 1 2最后逐个消总共 4 4 1 1 10 分。再看看更极端的做法先把最右边的单个 2 消掉得 1 分剩下 1 2 1 1此时把中间的 1 1 消掉得 4 分剩下 1 2最后再消 1 消 2总分 1 4 1 1 7 分反而不高。这个例子说明了一个很核心的事实消块的顺序会直接影响最终得分而且因为得分是“长度的平方”不是简单的线性相加把更多同色块攒到一起再一起消收益增长是非线性的。比如单独消 1 个得 1 分消 2 个得 4 分消 3 个得 9 分三块分开消是 3 分合并一起消是 9 分差距是三倍。所以这道题所有的难点都集中在“怎么用最优的顺序把同色块凑到一起消”上。这道题适合谁来刷我觉得是三类人第一类是刚学会区间 DP、想找经典题巩固的人第二类是准备面试时刷 LeetCode 546 移除盒子追溯原题的人第三类是想搞懂“为什么状态要多加一维 k”这个关键问题的人。题目的数据范围是 n 不超过 200暴力搜索完全不可能但也不是难到无从下手属于“想明白状态设计就通了想不明白就一直卡住”的典型题。1.2 为什么贪心写不出正解很多人第一次看到这道题第一反应是每次找最长连续同色段消掉得分最多是不是最优这个直觉在大部分随机数据下看着挺对但很快会被反例打脸。假设颜色序列是 1 2 1 1 2 2 1。最长连续同色段是 2 2长度 2先消掉得 4 分剩下 1 2 1 1 1此时三个 1 拼一起了得 9 分剩下 1 2再消得 1 1 2 分总分 15。但是换个策略先把右边的单个 2 消掉得 1 分剩下 1 2 1 1 2 1此时中间 1 1 可以消得 4 分剩下 1 2 2 1消 2 2 得 4 分剩下 1 1消掉得 4 分总分 13不如刚才。再试一种先消最左边的 1得 1 分剩下 2 1 1 2 2 1消 1 1 得 4 分剩下 2 2 2 1消 2 2 2 得 9 分最后消 1 得 1 分总分 15。和第一种一样。所以某些数据下贪心能碰巧拿到最优有些数据下不能。问题在于“优先消最长段”完全没有考虑消掉中间段之后两侧的相同颜色会不会拼出更长的段也没有考虑因为平方奖励把多个分散同色段攒到一起消可能更赚。这个“攒”的动作是有代价的代价就是中间那些不同颜色的块必须以某种方式提前消掉而它们的消除时机又会影响全局。贪心每一步只看局部天然无法处理这种跨区间的联动。这就是为什么一定要用动态规划。区间 DP 的好处是它能把“我先处理中间这一段让左右两边拼在一起”这个动作建模成状态转移不需要考虑全局顺序只需要保证子区间的最优解被正确计算。但普通的区间 DP 还不够因为这道题的“拼在一起”效应会跨越任意远的距离而且拼出来的长度必须计入状态否则后续计算没法得分。1.3 压缩预处理第一步几乎决定了这道题的生死写这道题之前有一个几乎是默认规定的预处理先把相邻且颜色相同的方块合并成一个“块”记录颜色和长度。比如原始序列 1 1 2 2 2 1 1 3 1压缩之后变成四段(1, 2)、(2, 3)、(1, 2)、(3, 1)、(1, 1)。注意这里第 1、3、5 段颜色都是 1但它们在原始序列中不相邻压缩不会把它们合并它们要等中间段被消掉之后才可能合到一起。为什么必须做压缩可以从两个角度理解。第一相邻的同色方块无论如何都是同生共死的你不可能只消其中一部分而不消另一部分因为你每次选择的是“连续相同颜色的段”既然相邻同色它们天然属于同一个可消段。把这一段拆开分别决策只是在浪费状态空间没有任何收益。第二压缩之后相邻段的颜色一定不同这给 DP 的枚举带来了极大的便利后面写转移时不需要反复检查“这段内部是否还能拆出同色子段”这种恶心问题。实现上也非常简单就是一趟扫描struct Block { int color; int len; }; vectorBlock seg; for (int i 0; i n; i) { int c; cin c; if (!seg.empty() seg.back().color c) { seg.back().len; } else { seg.push_back({c, 1}); } }压缩之后段数 m 一定小于等于 n。虽然最坏情况下 m n所有相邻方块颜色都不同但真实数据里通常 m 会小不少。后续所有 DP 都在压缩后的段上进行这就是整个题解的第一个关键决策。顺便说一句如果有人在没压缩的原始数组上写区间 DP状态会多出一维枚举段内长度代码会复杂很多而且很难写对这就是为什么我强调压缩几乎是“生死一步”。2. 核心状态设计dp[l][r][k] 是怎么被想出来的2.1 普通区间 DP 缺了什么如果用最普通的区间 DP 思路状态大概是 dp[l][r] 表示消掉区间 [l, r] 内所有方块能获得的最大分数转移时枚举中间分割点把区间分成两半左右分别消掉再加起来。这个想法在大多数区间 DP 题里都成立但放这道题上立刻出问题。问题出在“左右分别消掉”这个动作上。消掉左边的区间时右边的区间还在不在如果在它们会不会在某个时刻和左边的同色段拼起来普通 dp[l][r] 只记录“消光这个区间得多少分”完全不关心这个区间消完之后隔壁还剩着什么颜色的块、长度为多少。可这道题偏偏要求你关心如果你刻意留着区间右侧的一些同色块不消等左边处理完再一起消得分可能翻好几倍。这种“故意拖延”的行为在普通状态里根本没法表达。还是用例子说明。序列压缩成 (1, 1)、(2, 1)、(1, 2)颜色是 1 2 1 1。如果只看 dp[1][3]最优策略是先把 2 消掉得 1 分剩下 1 1 1再消得 9 分总分 10。此时 2 段被“夹在”两个长度为 2 的 1 段中间。如果换一种处理先消左边 2 段右边的 1 1得 4 分剩下 1 2消掉得 1 1 2 分总分 6。这告诉我们处理区间时区间右边的同色块可能在未来和区间内的同色段合并而在 dp[l][r] 里区间外部的情况是完全未知的。所以必须引入外部的信息。2.2 把“未来的同色块”装进状态标准解法引入了一个额外的维度 k状态写成 dp[l][r][k]。这里的 k 表示在处理区间 [l, r] 时这个区间的右侧已经额外附加了 k 个与第 r 段颜色相同的方块。也就是说压缩后的第 r 段本身长度是 len[r]再加上右侧外部还有 k 个同色方块它们现在是一个整体将来会一起消掉。dp[l][r][k] 的值就是“把区间 [l, r] 连同右侧这 k 个附加方块全部消干净能拿到的最大分数”。为什么选择“右侧附加”而不是“左侧附加”这不是随便定的。因为我们的计算方向是从左到右递进对某个区间左边的区间已经处理完了右边是尚未处理的未知部分。当右侧有同色块时把它们作为附加参数传进来正好符合“从左往右处理”的自然顺序。当然你也可以定义成左侧附加只要转移写对称就行但右侧附加是社区里最通用的写法调试和参考别人题解时更方便。这个状态设计的思想本质是把“未来才知道的信息”提前参数化。外部有多少同色块对当前区间来说是外部条件不是区间自己决定的但我们先把这些外部条件作为参数传给子问题让子问题在决策时能考虑到它们。这就是这道题最精华的地方学懂这个思想比背下代码重要得多。2.3 状态转移的两条路有了状态定义接下来就是转移。dp[l][r][k] 只有两种决策。第一种决策把右端第 r 段连同外部附加的 k 个同色块直接消掉。第 r 段的长度是 len[r]加上外部 k 个一共 len[r] k 个一起消掉得分是 (len[r] k)^2。消完之后区间 [l, r - 1] 内部就变得独立了右侧不再有附加的同色块所以需要求解 dp[l][r-1][0]。于是第一种转移是dp[l][r][k] dp[l][r-1][0] (len[r] k)^2第二种决策不在右端直接消而是把第 r 段和区间内部的某个同色段先“远程合并”。具体来说枚举一个位置 i满足 l i r 且第 i 段与第 r 段颜色相同。我们的做法是先把区间 [i1, r-1] 内部全部消干净这样第 i 段和第 r 段就拼到一起了同时右侧附加的 k 个同色块也拼到 r 段上所以拼完之后第 i 段右侧附加的同色块数量变成了 len[r] k。然后问题转化为处理区间 [l, i]且右侧附加 len[r] k 个同色块也就是 dp[l][i][len[r] k]。这一整条路线对应的转移是dp[l][r][k] max(dp[l][r][k], dp[i1][r-1][0] dp[l][i][len[r] k])这里的 i 必须满足 color[i] color[r]。注意区间 [i1, r-1] 被完全消掉时右侧没有附加条件所以是 dp[i1][r-1][0]不是 dp[i1][r-1][k]这是很多人写错的地方。它的物理含义是为了让第 i 段和第 r 段相遇必须把中间那段彻底消灭消灭时不能有任何外挂。这两个转移合在一起就是一个完备的决策集合。“直接消右端”处理了不合并的情况“枚举 i 合并”处理了攒同色块的情况。二者取最大值就是 dp[l][r][k] 的答案。最后题目要求的是整行方块全部消掉的最大分数即 dp[0][m-1][0]因为整行右侧没有额外方块k 0。3. 记忆化搜索实现与复杂度分析3.1 完整可提交代码理解了转移代码写起来其实很短。UVA 10559 原题的 n 200颜色值范围记不清具体上限但无所谓压缩后段数 m n三维 dp 数组开 [205][205][205] 足够。我习惯用记忆化搜索写这道题因为递归写法跟状态定义的思维方式一一对应比递推好调试太多。完整代码如下#include bits/stdc.h using namespace std; struct Block { int color; int len; }; vectorBlock seg; int dp[205][205][205]; int solve(int l, int r, int k) { if (l r) return 0; int res dp[l][r][k]; if (res ! -1) return res; // 决策一直接消掉第 r 段和右侧附加的 k 个同色块 res solve(l, r - 1, 0) (seg[r].len k) * (seg[r].len k); // 决策二枚举内部与第 r 段同色的第 i 段先消中间再合并 for (int i l; i r; i) { if (seg[i].color seg[r].color) { res max(res, solve(i 1, r - 1, 0) solve(l, i, seg[r].len k)); } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; for (int tc 1; tc T; tc) { int n; cin n; seg.clear(); for (int i 0; i n; i) { int c; cin c; if (!seg.empty() seg.back().color c) { seg.back().len; } else { seg.push_back({c, 1}); } } memset(dp, -1, sizeof(dp)); int m (int)seg.size(); cout Case tc : solve(0, m - 1, 0) \n; } return 0; }这段代码去掉输入输出和压缩核心逻辑不到十五行。这也是这道题的特点状态想通了代码短得让人惊讶状态没想到盯着题目看一天也写不出来。3.2 关键行逐行拆解记忆化数组 res 的引用写法int res dp[l][r][k]是记忆化搜索里特别顺手的小技巧后面所有对 dp[l][r][k] 的修改直接作用在数组上返回值时又自动带出结果省得每次手写dp[l][r][k] ...的赋值。不过要注意初始化问题memset dp 为 -1因为分数不可能为负-1 表示未计算。决策一的写法solve(l, r - 1, 0) (seg[r].len k) * (seg[r].len k)有两个细节值得强调。第一r 段被消掉之后区间 [l, r-1] 右侧不再有任何附加块所以第二个参数必须是 0 而不是 k。很多人第一直觉会把 k 继续传下去但这是错的。k 的意义是“第 r 段右侧附加的同色块”现在 r 段都没了k 自然消失了。第二得分计算用的是 len[r] k而不是 len[r] 的平方也不是 k 的平方。右侧那 k 个同色块虽然不属于区间 [l, r] 内部但它们会跟着第 r 段一起消所以必须一起算进长度。这是最容易丢分的地方也是决定答案正确性的关键。决策二的循环从 i l 到 i r找到第一个与第 r 段同色的段。注意不能枚举到 i r因为 i r 时没有“消中间区间”的过程那段区间是空的合并就没有意义而且会把问题绕回决策一。转移里solve(i 1, r - 1, 0)表示先消灭中间所有段这里同样不能传入 k中间段消灭时右侧没有附加。然后solve(l, i, seg[r].len k)表示第 i 段右侧现在附加了多少同色块答案是 seg[r].len k也就是说 r 段和外部 k 个全部附到 i 段后面。一个小验证如果 i 是距离 r 最近的同色段比如 i r - 1此时 solve(i1, r-1, 0) 得到 solve(r, r-1, 0) 0转移退化为 dp[l][r-1][len[r]k] 0这实际上表示第 r-1 段和第 r 段是相邻同色段但在压缩后这种情况不应该出现因为相邻同色段早就被压缩合并了。所以实际代码中 i r - 1 的情况只可能在颜色相同但压缩没合并的反事实下出现正常压缩后不会命中这个细节不用太纠结。3.3 复杂度为什么是高阶但能跑很多人看这个状态会慌dp[l][r][k] 三维l 和 r 各有 m 种k 最多 n状态数就是 O(m^2 * n)每个状态里还要循环枚举 i又乘一个 O(m)总复杂度 O(m^3 * n)。m 最坏等于 n 200那就是 200^4 1.6 * 10^9看起来要超时。但实际跑下来UVA 的时限完全能过。原因有几个。第一记忆化搜索访问不到所有理论状态。仔细想k 的取值不是任意的 0 到 n而是只可能是“若干个段的长度之和”这些长度来自决策二里 seg[r].len 的层层累加。不同的 (l, r) 组合能访问到的 k 值非常有限远达不到 n 种。第二枚举 i 时只找颜色相同的段实际数据里同色段的重复率没那么高循环往往很快就跳过了。第三测试组数有限UVA 的多组数据规模不算恐怖。如果你实在不放心也可以把 m 的三维数组开成 205静态数组快不用时清空用 memset实际表现很稳定。如果要更正式地分析通常把这题的复杂度写成 O(m^4) 的上界但在 n 200 的时候 m 往往远小于 n就算最坏构造优化过的记忆化搜索也能在几百毫秒内跑完。这一点也提醒我们分析复杂度不能只盯理论最坏要看状态之间是否有结构性的依赖限制。不过如果是递推写法就要非常小心循环顺序必须先计算短的区间再算长的区间k 作为第三维还得处理稍微麻烦所以我还是推荐记忆化搜索代码和思维都是最直接的。4. 实战避坑现场踩过的错误与排查记录4.1 最容易错的五个点第一忘记压缩。这里值得反复强调。直接在原始数组上写 DP状态会爆炸而且转移中要去判断“同一段内还能不能拆出同色子段”逻辑很容易出 bug。我早期有一版代码就是没压缩样例过了一交就 WA排查了半天才发现是压缩缺失导致某些状态被重复计算。第二决策一中把 k 的值算漏。比如写成了solve(l, r-1, k) seg[r].len * seg[r].len这是双重错误既丢了右侧附加块的得分又把本来应该归零的 k 传给了子区间。第三决策二中把附加数量写错。正确写法是solve(l, i, seg[r].len k)不是solve(l, i, k)。这是新手最容易犯的错逻辑上把 r 段和外部 k 个同色块都没合并进去答案自然偏小。第四中间区间的端点写错。应该是solve(i 1, r - 1, 0)有人会写成solve(i 1, r, 0)或者solve(i, r - 1, 0)这种错误会导致区间重复或漏段结果莫名奇妙。第五memset 初始化问题。如果 T 组数据每组都要清空 dp 数组忘了就 WA另外 -1 作为未计算标志没问题因为合法得分不可能为负数。4.2 小数据测试与状态打印写记忆化 DP 题我调试时最依赖的就是小数据暴力打表。比如 n 4 的序列 1 2 1 1手算最优应该是先把 2 消掉得 1 分剩下 1 1 1再消得 9 分总 10。直接跑代码如果输出不是 10说明转移有问题。定位问题最快的方式是在 solve 函数里加一个打印void debugPrint(int l, int r, int k, int val) { cerr dp[ l ][ r ][ k ] val \n; }然后在每个状态返回前调用一下。重点观察 k 比较大的状态是从哪条路径来的看看是决策一还是决策二产生的。比如 k 2 的状态 dp[0][0][2]它只能来自决策一处理 dp[0][1][0] 之后与某个同色段合并而来而不是凭空产生。如果打印出来的状态依赖关系不符合这个规律就说明转移有漏。另一个调试思路是写一个暴力搜索枚举所有删除顺序复杂度指数级但 n 很小时可以验证答案。用暴力结果去对照 DP 输出。这种对拍方式在算法题调试中非常有效尤其是 DP 这种“看着对但数值不对”的题。我碰到过一种情况是只有 n 取到 7 才出错这说明边界条件或者某个特定排列没有被小数据覆盖到这时候就要设计针对性数据比如所有颜色都相同的序列 1 1 1 1最优输出应该是 16因为一次全消 4 个得 16而不是分两次消 2 2 8。如果代码输出 8说明它没有把压缩后的长度利用起来大概率是压缩那一步出了问题。4.3 常见问题速查表为了节省大家调试时间我把高频问题整理成一张表问题可能原因排查方向结果偏小决策二附加数写成了 k 而不是 len[r] k打印状态检查转移参数结果偏大决策一中 k 传给子区间或压缩时错误合并了不相邻段检查 solve(l, r-1, 0) 中的 0样例过但 WA未压缩原数组状态冗余导致重复计算确认 seg 压缩后相邻段颜色不同时间超限没有记忆化或者循环枚举所有 i 时未跳过异色段检查 dp 初始化和 color 判断多组数据错乱dp 数组未清空或全局变量残留每组开始前 memset dp 为 -1还有一个隐藏比较深的错误反复递归中k 可能超过了数组第三维的大小。理论上 k 最大为所有段长度之和即 n所以 dp 数组第三维开 n 1 是足够的但如果你把压缩段总长当成 n 来开就会越界。比如原始 n 200压缩后 m 100但某个状态里的 k 累加长度可能接近 200不能只开 [105][105][105]第三维必须按原始 n 开。这个细节在小型题目数据下不容易暴露但一旦出现就是野指针级别的灾难。5. 从 UVA 10559 到同类题目的迁移5.1 LeetCode 546 移除盒子LeetCode 546 移除盒子几乎就是 UVA 10559 的换壳版题目描述改成点击一组同色盒子消除得分同样是长度的平方n 不超过 100。有了 UVA 10559 的基础这题就是直接套状态连压缩都可以不做因为 n 很小直接在原始颜色数组上跑 dp[i][j][k] 就行。不过注意LeetCode 上的代码风格通常要求函数式、返回值方便写递归加备忘录更合适。LeetCode 的测试用例里有一组经典数据颜色是 3 8 8 3 3 8 3 8 8最优答案是 71这个例子经常被拿来验证算法因为它包含多次“攒同色块”的动作。对着 UVA 题解改的时候只要把压缩逻辑删掉或保留都行保留压缩反而代码更快。两道题本质上是一道题理解了一道另一道就是复制粘贴的功夫。5.2 POJ 1390 与更多区间 DP 变体POJ 1390 Blocks 是 UVA 10559 的另一个孪生版本题目几乎一模一样数据范围也一样。如果你在某些 OJ 上搜 Blocks 题解会看到有人用 dp[i][j][k]其中 k 表示第 j 段右边有多少个和它同色的连续块这就是这道题的同一套思路。这些题解里对 k 的定义可能有一点点表述差异有的写成“额外附加的长度”有的写成“右侧剩余同色块数”本质相同看代码时要小心别因为表述不一样就以为它们是不同算法。除了同卵双胞胎这条思路还能迁移到不少变体题上。比如某些题目把得分改成“消除长度乘一个系数”或“消除长度加固定值”状态设计不需要变只改得分函数。再比如有的题要求你输出具体消除方案那就需要额外记录转移来源也就是在每个状态算出最大值时记下是从哪条转移路径来的等所有状态算完后回溯一次。5.3 这种“加一维状态”的思考方式还能用在哪这道题教给我们的不只是一个 DP 模板更是一种状态设计哲学如果当前区间的结果会受外部无关区域的影响就把外部影响参数化成一个新维度。这个思想在很多更高级的题目里反复出现。举一个例子字符串编辑类 DP 中当删除或替换操作会影响后续匹配长度时有时需要额外记录“后面还欠多少个未匹配的字符”这就是加一维的思路。再比如括号序列相关的 DP计算到某个位置时还需要知道前面有几个未匹配的左括号这也是额外一维。还有背包问题里的“额外容量”概念本质是把未来可能的资源需求当作状态维度。UVA 10559 Blocks 是理解这个思想的最小而美的载体所以它被无数教程当作区间 DP 进阶的第一课。如果你能把这个 k 的本质想透再看那些复杂的多维 DP会发现它们都是同一个道理状态不只是“我处理了哪些东西”还包括“处理完后对未来的影响是什么”。我个人在实际操作中还有一个小技巧先用递归暴力写一版正确但慢的代码再用 dp[l][r][k] 去套过程中就能自然理解为什么 k 是必要的。这道题我前前后后刷过好几遍每过一段时间重新写都会对“把未知量参数化”有更深一层的体会。如果你现在卡在转移上我建议你放下代码先拿笔在纸上模拟一次 k 0 到 k 2 的合并过程把每一步谁和谁拼在一起写清楚思路很快就会打开。祝你能从这道题里真正收获那个关键的感觉毕竟这种题目一旦通了后面的很多 DP 都会变得顺畅起来。