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; }; vector<Block> 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 段颜色相同。我们的做法是：先把区间 [i+1, 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[i+1][r-1][0] + dp[l][i][len[r] + k])
这里的 i 必须满足 color[i] == color[r]。注意区间 [i+1, r-1] 被完全消掉时，右侧没有附加条件，所以是 dp[i+1][r-1][0]，不是 dp[i+1][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; }; vector<Block> 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(i+1, 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 都会变得顺畅起来。
