看到 LintCode 3870 这道题时我第一反应是“又来一个回文题”于是随手写了段判断回文的代码果然提交后直接翻车。后来认真把题目读了一遍才反应过来它要的不是“判断某个数组是不是回文”而是“每次允许删除任意一段连续的回文子数组求清空整个数组的最少步数”。很多人现在喜欢直接把题目丢给豆包这类 AI 助手拿回来一个public int minimumMoves(int[] nums)模样的代码就交但如果对删除规则理解不到位换个测试用例照样挂。这篇我打算把这道题从头到尾拆开讲从回文子数组的准确含义、为什么贪心不靠谱、区间 DP 的状态怎么设到一份能直接提交的 Java 实现最后再聊一个刷题时几乎人人都会遇到的附加话题本地调试时怎么把int[]转成可读字符串包括 Qt 场景下 int 转 QString 的坑。1. 这道 LintCode 3870 到底在问什么删除规则决定 DP 方向1.1 三个最容易理解错的地方题目给的原型是public int minimumMoves(int[] nums)入参是一个原生int[]返回值是最少操作次数。这个签名本身不复杂复杂的是“删除回文子数组”这六个字里藏着的三个细节。第一个细节是“子数组”必须是连续的。你可以选中数组中任意一段连续区间但不能像子序列那样跨着选。比如[1, 2, 1]里的[2, 1]和[1]是子数组而[1, 1]就不是子数组因为它不连续。第二个细节是删除之后数组会拼接。这个很多人会忽略。假设数组是[1, 2, 3, 1]先删掉中间的[3]数组变成[1, 2, 1]这时[1, 2, 1]本身就是回文可以一次性删掉。如果在“分割回文串”那类题里[3]删掉后1和2不会自动靠拢但在本题里它们会这就是很多解法写成区间 DP 的根本原因。第三个细节是单个元素永远是回文。所以答案永远存在最坏情况是每个元素单独删一次也就是n步。这样我们才能放心讨论“最少”的问题否则题目可能无解。1.2 几个手算样例建立直觉先看四个典型样例。输入 nums最少步数一种可行的删除顺序[1, 2, 2, 1]1整段本来就是回文直接删[1, 2, 3, 2, 1]1整段本来就是回文直接删[1, 2, 3, 1]2先删中间的[3]剩下[1, 2, 1]再删[1, 2, 1, 2]2先删[1, 2, 1]剩下[2]再删第一个和第二个样例说明如果整段是回文答案就是一不需要做任何拆分。第三个样例说明即使整段不是回文也可以通过先删中间元素让剩下的部分重新拼成回文。第四个样例说明当数组里有两个相同值被其他元素隔开时先删掉能形成回文的较大部分往往比逐个小块删除要省步数。这三个样例里最接近 DP 雏形的是[1, 2, 3, 1]和[1, 2, 1, 2]。它们的共同点是最终答案不是简单地把数组分成左右两块各自删除而是某些元素会跨越原来的区间边界在后续拼接中合并成同一次删除。这就是为什么不能只做“从左往右一个个删”的线性模拟。1.3 数据规模决定解题方向LintCode 的隐藏测试一般不会把数组长度给得特别夸张这种区间 DP 题通常nums.length在几百的量级。我按常见经验判断这种规模下O(n^2)的空间和O(n^3)的时间是可以接受的。如果题目把长度放到 1000 以上那就要考虑用递归记忆化或者其他优化方式但先掌握最经典的区间 DP 写法对绝大多数情况已经够用。做题之前我建议先给自己定一个原则不要急着写代码先在纸上把“删除后拼接”的过程画出来。这个习惯能省掉后面很多调试时间。2. 先说为什么不靠谱的贪心区间 DP 的 dp[i][j] 可以这样定2.1 为什么贪心很容易翻车第一次接触这道题我本能地想每次都找最长的回文子数组删掉是不是就是最优后来试了几个用例发现很难找到一个能严格证明最优的贪心策略原因在于“删除后拼接”会让后续状态发生改变。比如数组[1, 2, 1, 2]如果按“优先删当前最长回文”来做最长的回文是[1, 2, 1]删掉后剩[2]两步搞定看起来没问题。但如果你换一种贪心规则比如“优先把相同值配对删除”处理[1, 2, 1, 2]时就会很尴尬因为两个1不相邻两个2也不相邻你不能直接配对。贪心策略的另一个问题是你先删掉某一个回文块后原本可以和新拼接产生的回文配对的两个元素可能就再也凑不到一起了。这种“跨删除顺序产生的新机会”很难被一个局部决策覆盖。我试过几种常见贪心思路比如优先删最短的、优先删两端的、优先删当前最长的都能在特定用例上表现不错但换一个用例又不行。原因很简单这类题的最优解本质上是给删除顺序做全局规划而贪心只看到当前这一步。真正稳妥的做法不是猜贪心而是把问题建模成区间分治对于一个连续区间nums[i..j]我们只关心把它完全删干净需要的最少步数不考虑外面的元素怎么删。2.2 dp[i][j] 的状态定义为什么合理定义dp[i][j]表示把原数组中下标从i到j这一段连续子数组完全删掉所需要的最少步数。最终答案就是dp[0][n - 1]。这个定义天然支持“拼接”的语义因为当我们只处理[i, j]时区间内的元素是连续的区间外的东西不会影响内部删除过程。更关键的是删除过程中如果内部元素被删掉剩下的元素会靠拢而这种靠拢发生的位置仍然在[i, j]的范围内。为什么区间 DP 而不是线性 DP原因是删除操作可能同时覆盖一个区间的左右两侧。比如[1, 2, 1]整段删一次这时候你没法把它拆成“先删左边一截再删右边一截”来独立处理因为首尾的1需要同时出现才能合并成一次删除。区间 DP 的长处就是通过枚举长度、枚举起点、讨论左右端点是否相等把“跨越左右的合并”显式表达出来。状态数量是O(n^2)每个状态转移时要枚举分裂点所以总体复杂度是O(n^3)。这个复杂度对几百长度的数组完全没问题。2.3 需要记住的一个反直觉结论区间 DP 里最反直觉的结论是当nums[i] nums[j]时dp[i][j]不一定比dp[i 1][j]大反而可能更小。因为左右两个相等的端点可以“搭便车”它们可以和内部最后一次形成的某个回文块一起合并成一次更大的删除操作。这个思想是后面转移方程的核心。如果你已经看懂了这一点那么三分之一道题已经拿下了。3. 转移方程与 minimumMoves 的 Java 实现一个可直接提交的版本3.1 转移方程的两个动作标准的区间 DP 转移需要覆盖两种情况。第一种是“拆分”。把区间[i, j]从某个位置k切成左右两段[i, k]和[k 1, j]左边删干净需要dp[i][k]步右边删干净需要dp[k 1][j]步那么总步数是两者之和。枚举所有可能的k取最小值dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j])这个式子保证任何一个“先把左右两块分别删完”的方案都能被覆盖到。几乎所有区间 DP 都有这一步它是分治思想的直接体现。第二种是“合并”。当nums[i] nums[j]时左右两个端点相等它们有机会和内部最后一次删除操作合并成同一次。这时的转移是dp[i][j] min(dp[i][j], dp[i 1][j - 1])理解这个式子要回到“最后一次删除”这个视角。假设内部区间[i 1, j - 1]已经用了dp[i 1][j - 1]步删干净那么最后一次删除内部某个回文块时内部剩余部分本身一定是一个回文块。既然nums[i] nums[j]我们在那次删除操作里把左右两个端点和内部的这个回文块一起包进来组成更大的回文一次操作就同时删掉了端点。所以端点本身不会增加新的步数。这就是为什么dp[i][j]可以直接取dp[i 1][j - 1]而不是dp[i 1][j - 1] 2。3.2 边界条件怎么处理边界有两种情况需要单独想清楚。长度 1 的子数组只有一个元素它一定是回文所以dp[i][i] 1长度 2 的子数组有两个元素。如果两个元素相等那么[x, x]本身是回文一次删除搞定如果两个元素不等那么只能各删一次需要两步if (nums[i] nums[j]) dp[i][j] 1; else dp[i][j] 2;这里必须单独写len 2因为如果直接用合并转移dp[i 1][j - 1]会出现dp[i 1][i]这种没有意义的状态下标会乱掉。很多第一次写的人在这里越界所以我把长度 2 单独拎出来。3.3 完整代码与手算验证下面这段代码可以直接在 Java 的 LintCode 环境中提交public int minimumMoves(int[] nums) { int n nums.length; if (n 1) { return n; } int[][] dp new int[n][n]; for (int i 0; i n; i) { dp[i][i] 1; } for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (len 2) { dp[i][j] (nums[i] nums[j]) ? 1 : 2; continue; } dp[i][j] Integer.MAX_VALUE; if (nums[i] nums[j]) { dp[i][j] Math.min(dp[i][j], dp[i 1][j - 1]); } for (int k i; k j; k) { dp[i][j] Math.min(dp[i][j], dp[i][k] dp[k 1][j]); } } } return dp[0][n - 1]; }手算一遍nums [1, 2, 1, 2]来验证。长度 1全部是 1。 长度 2dp[0][1] 21 和 2 不等dp[1][2] 22 和 1 不等dp[2][3] 21 和 2 不等。 长度 3dp[0][2]两端都是 1取dp[1][1] 1表示[1, 2, 1]可以一次删完。dp[1][3]两端都是 2同理取dp[2][2] 1。 长度 4dp[0][3]两端是 1 和 2 不相等走拆分枚举。当k 0时dp[0][0] dp[1][3] 1 1 2当k 2时dp[0][2] dp[3][3] 1 1 2。最终答案是 2。这个结果和手算一致先删[1, 2, 1]再删剩下的[2]。3.4 复杂度和一个容易忽略的小问题时间上是三重循环枚举区间长度、枚举起点、枚举分裂点所以是O(n^3)。空间上是二维数组O(n^2)。在n为几百的情况下跑起来没什么压力。有一个小问题要提醒初始化dp[i][j] Integer.MAX_VALUE时如果后续代码质量不过关可能出现dp[i][k] dp[k 1][j]先算出来一个超大值再加另一个值。本题中dp的最大合理值不会超过n所以用Integer.MAX_VALUE做初始哨兵不会溢出但如果你把初始值设成Integer.MAX_VALUE - 1会更保险。我更习惯用Integer.MAX_VALUE因为转移时要么被覆盖要么由于长度限制能保证所有状态都能被正确算出来。4. 本地验证时 print 数组的三种姿势以及 int 转 QString 的编译坑4.1 为什么本地需要打印数组和 dp 表刷题时最烦的不是写不出代码而是写出来之后不知道对不对。很多 LintCode 的题没有本地调试环境你只能靠main方法自己造用例。我在做这道题时第一版代码跑在[1, 2, 2, 1]上没问题但跑[1, 2, 3, 1]就出错。当时我做的就是写完minimumMoves之后在测试代码里打印出整个dp表一列一列核对。如果没有打印我只能凭感觉猜哪里错了凭空猜状态转移几乎不可能。这个看起来机械的“打印数组”动作在实践中比想象中重要。所以这里集中整理三种把int[]变成可读字符串的写法。4.2 Java 里打印 int[] 的快捷方式Java 最省事的办法是用Arrays.toStringimport java.util.Arrays; int[] nums {1, 2, 1, 2}; System.out.println(Arrays.toString(nums));输出[1, 2, 1, 2]如果是二维数组想打印 dp 表我建议自己写一个小函数比如private static void printMatrix(int[][] dp) { for (int[] row : dp) { System.out.println(Arrays.toString(row)); } }这样每一行就是一个子区间的答案竖着看就是长度递增的过程。我实际排查转移方程时经常是盯着某一行看为什么dp[0][3]算出来是 3但手算是 2。对比打印结果和手算表格很快能定位到是哪一段转移没走对。4.3 刷题时常见的 int 转 QString 需求最近“int 转 QString”这个搜索词很热原因也简单不少刷题的人会用 Qt 或者 C 写本地测试然后用qDebug()打印数组。qDebug()打印QString很方便但你拿到的数据是int这就绕不开转换。最直接的写法是int value nums[i]; QString s QString::number(value);如果你想把一个int数组拼成一行字符串可以这样QStringList parts; for (int value : nums) { parts QString::number(value); } qDebug().noquote() parts.join(, );这里有个很多人第一次写 Qt 时必踩的坑直接写QString int会编译失败。比如QString s index: i; // 错i 是 int不能直接加正确做法是先转成QString再拼接QString s index: QString::number(i);或者用带参数格式化的argQString s QString(index: %1).arg(i);如果你希望输出固定宽度、补零的数字arg还能这么写QString s QString(%1).arg(i, 3, 10, QLatin1Char(0));这个写法表示把i按十进制输出宽度至少 3 位不够就补0。比如i 7时输出007。刷题时偶尔要排列对齐 dp 表这个功能比手动补零省事。4.4 Qt 场景下打印 dp 表的小模板如果你真的在 Qt 环境里刷题可以写一个小的辅助函数void dumpMatrix(const QVectorQVectorint dp) { for (const auto row : dp) { QStringList parts; for (int v : row) { parts QString::number(v); } qDebug().noquote() parts.join( ); } }这里每一列之间的距离用两个空格拉开比逗号更适合看矩阵。这份代码的关键点只有两个一是QStringList存放每一行的字符串片段二是QString::number负责把int安全转换。如果你直接拿QString接一个intQt 的编译器会明确告诉你没有匹配的重载函数报错信息还会指向QString那一堆构造函数很容易把人看晕。所以记住一条经验在 Qt 里所有从数字到字符串的转换优先写QString::number(...)别偷懒用隐式转换。5. 举一反三回文删除类题型背后的区间分治套路5.1 这类题为什么都长一个样区间 DP 的套路其实很固定先枚举区间长度再枚举区间起点然后讨论端点的合并方式或者枚举分裂点。这个框架在 LeetCode 1246 删除回文子数组、LeetCode 312 戳气球、LeetCode 1039 多边形三角形最低得分这些题里都能看到。它们的共同点是决策都会影响到后续元素的相对位置所以不能用简单的从左到右扫描解决。你只能把问题收敛到一个连续区间内然后用“最后一步删除什么”或者“最后一个处理的块是谁”这个角度来设计转移。拿本题举例转移方程的两种动作本质上就是回答两个问题这个区间要不要拆成两半分别处理如果左右端点相等它们能不能在最后一次删除中和内部一起被干掉能把这两个问题回答清楚代码基本就出来了。很多题看起来难实际是这两个问题的排列组合。5.2 我自己的做题流程我做这道题花了大概四十分钟其中有一半时间都花在对着[1, 2, 3, 1]手写删除过程上。最后总结出一个稳定可行的流程分享给你参考。第一步先不要想优化把最基本的样例在草稿纸上画一遍。题目里给的示例往往意味着某种边界情况[1, 2, 3, 1]这个例子就是典型的“先删中间再删外围”它会直接提示你左右端点可以合并。第二步定义dp[i][j]时把“删干净”这个动作的含义写清楚。不是“删掉多少元素”而是“让 i 到 j 这一段从数组里消失需要几步”这样才能避免后续把区间长度当成答案。第三步先写递归记忆化版本再改成自底向上的循环。递归版本的好处是转移自然不容易遗漏状态。比如本题可以写private int dfs(int l, int r, int[] nums, int[][] memo) { if (l r) return 0; if (l r) return 1; if (memo[l][r] ! 0) return memo[l][r]; int res 1 dfs(l 1, r, nums, memo); for (int k l 1; k r; k) { if (nums[l] nums[k]) { res Math.min(res, dfs(l 1, k - 1, nums, memo) dfs(k 1, r, nums, memo)); } } return memo[l][r] res; }这个版本和前面循环版本的转移不完全一样它依赖一个关键观察nums[l]要么单独删要么和后面某个相同的nums[k]一起在某个删除操作中消失。两种写法都是对的区别只是你从哪一头看问题。我建议你先看懂一个版本然后自己把另一个版本推一遍这样整个状态空间的形状才能真正长在脑子里。第四步用几个典型用例回归验证。我一般会准备四类用例整个数组本身就是回文答案必须是 1数组完全没有任何长度大于 1 的回文答案必须是 n数组有两个相同值被隔开答案可以小于 n空数组或者长度为 1 的数组边界返回 0 或 1。如果这四类都没问题提交时基本不会在边界问题上丢分。5.3 后面还能怎么扩展如果你把本题吃透下一步可以去看 LeetCode 546 移除盒子。那题也是区间 DP但状态要额外加一个维度因为连续相同颜色的盒子还会和区间外面的同色盒子合并。本题的“端点相等合并”思想就是移除盒子那道题的一个简化版。另一个可以扩展的点是如果把回文子数组改成回文子序列答案会完全不同因为删除回文子序列时你可以任意挑选跨位置的字符递归结构更接近最长回文子序列。做题时先分清“子数组”和“子序列”再决定用区间 DP 还是线性 DP这个判断比背模板更重要。最后再分享一个实际体会刷区间 DP 题最忌讳一上来就套模板。换一道题转移方程里那两三个dp下标很容易写错一个字符导致整个答案错误。我现在的习惯是先在纸上手算一个长度为 4 或 5 的小数组把 dp 表写出来再对照代码跑出同一个结果最后才提交到判题环境。这个过程看着笨但比反复提交试错快得多。毕竟判题环境不会告诉你“你的合并转移少写了一个 k”它只会给你一个红色的 Wrong Answer。