LeetCode 1312这道题我每次带新人刷到它的时候都会多说一句别看它标着Hard其实它是一道非常典型的区间动态规划题目核心问题就那一句话——给你一个字符串s你可以在任意位置插入任意字符问最少插入多少次能让它变成回文串。等你把“插入”这个动作想透了后面的状态设计几乎就是顺水推舟。这篇博文我会从题意拆解、状态推导、二维DP到一维优化完整讲一遍再附上调试经验和同类题对照表。适合刚把基础DP刷完、想系统啃下区间DP题型的人也适合面试前突击字符串动态规划的同学。1. 题目概述与核心思路拆解1.1 为什么这道题看起来难难点到底在哪先过一遍题目的原始定义一个字符串是回文串当且仅当它从前往后读和从后往前读是一样的比如aabaa、abba都是回文串而abc不是。现在给你任意字符串s允许你在任何位置插入任意字符最终要让s成为一个回文串求最少插入次数。很多人第一反应是这有什么难的从左往右扫遇到不匹配就补一个字符不就行了我当年第一次做这题也是这么想的结果自己举几个例子就翻车了。比如mbadms[0]m和s[4]m相等中间是bad再看bad首尾b和d不相等如果在末尾补一个b得到badb但这还是不对称的因为还要处理内部的a。这里就引出了关键问题每次处理两端不匹配的字符时可以在左端补一个和右端相同的字符也可以往右端补一个和左端相同的字符但选择哪一侧会影响后续子问题的规模所以它不是一道贪心题而是一道需要枚举两种选择的动态规划题。这道题之所以是困难不是因为状态方程本身难推而是因为它需要你跳出“从整体移动”的直觉转而意识到回文串的构造可以只看两端字符内部交给子问题。这个思维转变很多人一开始绕不过来。1.2 从几个例子感受一下“最少插入”在做什么先拿字符串a来说它自己就是回文串不需要插入答案是0。aa也是回文串答案是0。ab呢两个字符不相等只需插入一个字符就能变成aba或者bab答案是1。再来个复杂点的例子mbadm从两端看m和m相等那两端的m就可以直接成为最终回文串的最外层内部只需要把bad处理成回文串。bad首尾b和d不等有两种策略在左侧补一个d变成dbad内部ba还需处理或者在右侧补一个b变成badb内部ad还需处理。无论哪种最终都需要再处理一个长度为2的子串。依次推进你手动试一遍会发现至少需要插入2次这也是官方的示例答案。手动推演的意义在于它精确地对应了动态规划的子问题划分——s[i]等于s[j]时问题规模缩减为s[i1:j-1]s[i]不等于s[j]时问题规模缩减为s[i1:j]或s[i:j-1]并加1次插入。如果你能把这个过程复述出来其实转移方程已经写了一大半。1.3 为什么区间DP是这类题的“标准答案”回文串有一个天然特征你判断子串是否回文、构造子串回文时总是从两端向中间收缩或者从中间向两端扩展。这种“通过区间两端状态推导整个区间状态”的思路正是区间DP的典型应用场景。对比一下常见的线性DP比如最长递增子序列状态转移是dp[i] max(dp[j] 1)它只依赖前缀信息而回文类问题dp[i][j]往往依赖dp[i1][j-1]、dp[i1][j]、dp[i][j-1]这些“相邻更小区间”的状态。换句话说要计算一个大区间必须先知道所有小区间的答案这种依赖关系决定了我们必须按区间长度从小到大遍历。这道题和LeetCode 516“最长回文子序列”的思考路径几乎一样区别只在于一个是求“最长”一个是求“最少插入”理解了其中一个另一个就是顺手的事。2. 动态规划设计与状态转移推导2.1 先脑内写一个递归版本理解状态含义很多题解上来就给你dp[i][j]但为什么是dp[i][j]我习惯先把问题写成递归函数定义一个函数f(i, j)表示把子串s[i:j]闭区间变成回文串所需的最少插入次数。那么如果i j说明子串为空或只有一个字符它天然是回文串返回0。如果s[i] s[j]两端已经匹配不需要在这两个字符上做任何插入直接返回f(i 1, j - 1)。如果s[i] ! s[j]要么在左侧插入一个和s[j]相同的字符让新字符和s[j]配对然后继续处理s[i:j-1]要么在右侧插入一个和s[i]相同的字符让新字符和s[i]配对然后继续处理s[i1:j]。两种方案都算一次插入取两者较小值再加1即min(f(i 1, j), f(i, j - 1)) 1。这个递归版本虽然直观但会有大量重复计算比如f(0, 4)和f(1, 5)都会去算f(2, 4)。所以我们要把它转成带备忘录的递归或者直接写成自底向上的动态规划。转化的过程就是状态定义固定下来的过程dp[i][j]表示子串s[i:j]变成回文串的最少插入次数。2.2 状态转移方程以及为什么不用考虑“补多个字符”的情况正式的状态转移方程就两行当s[i] s[j]时dp[i][j] dp[i 1][j - 1]当s[i] ! s[j]时dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1初次看到这个方程的人最容易问一个问题如果s[i] ! s[j]我为什么只考虑“补一个字符”带来的两种分支而不是考虑“补多个字符”其实不需要因为每次插入操作只解决一对端点的匹配问题。你补一个字符让其中一个端点被抵消剩下的还是一个规模更小的子串重复这个过程子串持续缩小直到不需要插入为止。每次迭代解决一对端点累计的插入次数就是答案所以每次转移只加1就足够了。另一个容易纠结的点是dp[i][j]在s[i] s[j]时为什么不加1因为端点本身已经对称相等了它们可以直接成为最终回文串的最外层不需要为新字符付出代价。哪怕内部的dp[i1][j-1]需要若干次插入这些插入也不会影响端点的配对关系所以直接继承即可。我把两种情况整理成表格看着更清楚当前两端字符关系操作方式转移方程直观理解s[i] s[j]不需要插入dp[i][j] dp[i1][j-1]两端已经配对只处理中间s[i] ! s[j]左侧补一个s[j]dp[i][j] dp[i][j-1] 1新字符和右端配对处理s[i:j-1]s[i] ! s[j]右侧补一个s[i]dp[i][j] dp[i1][j] 1新字符和左端配对处理s[i1:j]2.3 初始化、遍历顺序以及一个特别容易踩的边界坑接下来是写代码前必须想清楚的三个点。第一初始化。dp[i][i] 0因为单个字符天然是回文串。更准确地说所有长度小于等于1的区间结果都是0。在二维数组里我们一开始把所有元素初始化为0即可因为dp[i][j]只有在j i时才会被真正计算。第二遍历顺序。区间DP的黄金法则是从小到大枚举区间长度。你可以写成外层循环i从大到小、内层循环j从小到大也可以显式地按长度len从2到n枚举。前者写起来更简洁但新手容易搞混。为什么i必须从大到小因为dp[i][j]依赖dp[i1][j]和dp[i1][j-1]也就是依赖行号更大更靠下的区间。如果i从小到大遍历那么计算dp[i][j]时dp[i1][j]这一行还没被算出来状态就是错的。第三边界坑。当s[i] s[j]且区间长度为2时比如子串aa状态转移会用到dp[i1][j-1]也就是dp[i1][i]。这个下标在语义上是一个空区间值应该是0但在二维数组里dp[i1][i]通常是未定义或者说是数组对角线左下方的位置可能根本没被赋值过。所以在代码里要加一个判断当j - i 2时才取dp[i1][j-1]否则直接取0。这个问题几乎每个人写第一版都会遇到。3. 完整代码实现与实操细节3.1 二维DP版本最容易理解先跑通再说先把最直观的二维版本写出来。Python代码如下class Solution: def minInsertions(self, s: str) - int: n len(s) dp [[0] * n for _ in range(n)] for i in range(n - 2, -1, -1): for j in range(i 1, n): if s[i] s[j]: # 区间长度大于等于2时才有内部子串 dp[i][j] dp[i 1][j - 1] if j - i 2 else 0 else: dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1 return dp[0][n - 1]C版本长得也差不多class Solution { public: int minInsertions(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); for (int i n - 2; i 0; --i) { for (int j i 1; j n; j) { if (s[i] s[j]) { dp[i][j] (j - i 2) ? dp[i 1][j - 1] : 0; } else { dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1; } } } return dp[0][n - 1]; } };这段代码的时间复杂度是O(n^2)空间复杂度也是O(n^2)。给定题目中s.length 500的限制二维数组毫无压力LeetCode实测大概在几十毫秒级别。我建议第一次接触这道题的人先把这个版本理解透、跑通所有示例再去做优化。验证一下几个用例s a返回0s ab返回1s aa返回0s mbadm返回2s leetcode返回5。其中leetcode这个官方示例手动模拟比较繁琐但跑一遍代码就能看到结果。如果你写的是二维版本建议本地加几个print把dp矩阵打出来观察一下对角线附近的值和边界判断是否正确这对排查遍历顺序问题特别有帮助。3.2 一维滚动数组优化省空间但pre变量是关键二维DP虽然好懂但面试时如果你能写出一维优化版本会加分不少。优化的依据是状态转移里依赖关系很集中dp[i][j]只用到了dp[i1][j]、dp[i][j-1]和dp[i1][j-1]。换句话说当前行只依赖下一行和当前行自己更早的行用完就再也不会被引用了。那我们可以只保留一维数组dp[j]让它表示当前i行、第j列的值。class Solution: def minInsertions(self, s: str) - int: n len(s) dp [0] * n for i in range(n - 2, -1, -1): pre 0 # 对应 dp[i1][i]也就是空区间 for j in range(i 1, n): temp dp[j] # 旧的 dp[i1][j]要先保存 if s[i] s[j]: dp[j] pre # pre 就是 dp[i1][j-1] else: dp[j] min(dp[j], dp[j - 1]) 1 pre temp return dp[n - 1]这段代码里最绕的就是pre变量。我拆开讲一下它的作用。在一维数组中当外层循环从i变到i-1时dp[j]被更新后原本“下一行”的信息就丢了。但状态转移需要用到dp[i1][j-1]也就是“下一行、左一列”的值。这个值本质上是上一轮外层循环时dp[j-1]的旧值。所以我们在更新dp[j]之前先用temp保存旧的dp[j]更新完dp[j]后再把pre更新为temp。这样进入下一个j时pre恰好就是当前i1行对应j-1位置的值。每一步都不能错位错一位结果就会乱七八糟。为了看清楚我建议你拿s abca这种短字符串手动把每一轮pre和dp的变化列出来跑两遍就懂了。这也是我调试一维版本时最常用的方法。3.3 一个巧妙的等价解法n 减去最长回文子序列长度做这题的时候我搜过不少题解发现有人提到一个等价结论最少插入次数等于字符串长度减去它本身的最长回文子序列长度。比如mbadm长度为5它的最长回文子序列是mam或mbm长度3所以最少插入次数是5 - 3 2和DP结果一致。leetcode长度为8最长回文子序列长度是3比如eetee或eetee最长好像更长实际上leetcode里最长的回文子序列是eetee不对leetcode字符有l,e,e,t,c,o,d,e最长回文子序列应该是etete? 我手动算一下l e e t c o d e能组成的回文子序列e和e配对t或其它最长的可能是etete? 但字符里只有一个tete或者eee是3所以最长可能eetee? 没有第二个t所以最长可能eedee? 没有d的位置合理最多是eee或ete长度38-35与官方示例5一致。这个结论很漂亮但我不建议直接用这个作为第一思路因为它绕过了对“插入”过程的理解直接套另一个DP问题的答案。如果你还没做过516题理解起来会有断层。更好的姿势是先把1312的区间DP方程吃透再把这个等价关系当成验证手段。两道题放一起刷效果特别好。4. 常见错误、同类题型对照与调试技巧4.1 我在调试中遇到的高频Bug速查表这道题的代码不长但错误率不低。我整理了一些自己踩过、也看别人踩过的坑错误现象根本原因解决办法结果总是比答案小1计算s[i] s[j]时直接用了未初始化的dp[i1][j-1]长度2的区间边界没处理好加j - i 2判断或单独初始化长度为1的区间结果特别大接近n外层i从小到大遍历dp[i1][j]还是0导致转移依据错误外层i必须从n - 2递减到0一维版本结果和二维不一致pre保存的是错误位置的旧值导致dp[i1][j-1]取错打印每一轮的pre和dp对照二维矩阵逐项排查字符串全是相同字符时结果不为0没有正确识别s[i] s[j]分支错误走了min 1aaaa这类用例加进去作为回归测试其中“结果比答案小1”的问题最常见因为当j - i 1时dp[i1][j-1]在语义上是一个空串直接取0才对。很多新手在二维数组里访问dp[i1][i]时虽然不越界但这个值其实是0因为初始化全0所以某些情况下碰巧正确某些情况下会出问题。更好的习惯是显式处理。4.2 回文串DP题型的通用套路记住“两端比较区间收缩”做完1312你可以顺手把LeetCode里一系列回文串动态规划题放一起复习它们共享同一个套路用两端字符的比较结果决定如何收缩区间。题目问法DP含义转移方向516 最长回文子序列最长回文子序列长度dp[i][j]表示s[i:j]内最长回文子序列长度s[i]s[j]时加2否则取单侧较大值1312 让字符串成为回文串的最少插入次数最少插入次数dp[i][j]表示s[i:j]变回文的最少插入次数s[i]s[j]继承内部否则min15 最长回文子串最长回文子串本身布尔数组标记是否回文由短区间推导长区间132 分割回文串II最少分割次数一维dp[i]表示前i个字符的最少分割配合回文预处理你会发现这些题的思考起点都是同一个问题“子串s[i:j]是否回文 / 变成回文需要多少操作”。一旦掌握了“由内向外扩展、由短到长递推”这个框架回文串DP基本就是一通百通。4.3 现场手写代码时的Checklist如果面试时遇到这道题我会按下面这个顺序推进避免手忙脚乱和面试官确认题意复述一遍“在任意位置插入任意字符求最少次数”。先抛递归思路f(i, j)定义、三种分支。点明这题是区间DP因为子问题天然是子串区间。写出转移方程和初始化规则讲清楚为什么i从大到小、j从小到大。先写二维版本跑通示例如果时间允许再提一维优化的思路并实现。主动补测试用例单字符、双字符、完全回文、完全逆序字符串。这个顺序能最大限度避免“还没想清楚就上手写代码”的失误。尤其是第4步很多人一上来就写循环结果遍历顺序错了浪费大量调试时间。5. 刷题之外的几点想法这道题做多了之后我自己的体会是困难题和中等题的差距往往不在于公式复杂而在于你能否快速识别出它属于哪个模型。1312就是一个很好的例子——它披着“插入字符”的外衣内核却是最经典的区间DP。如果你能把“插入”翻译成“两端配对”把“最少次数”翻译成“子问题取最小”这道题瞬间就变成了模板题。还有一个实操层面的小技巧刷这类题时本地准备一个测试函数把官方示例和几个自造边界用例一次性跑完。我写LeetCode题解时经常用abc、aba、abca、tcejorpt这类字符串做冒烟测试覆盖了完全回文、完全逆序、部分匹配等情况。跑一遍只要几秒钟但能帮你免去一次次提交试错的尴尬。最后再分享一个扩展方向如果题目改成“只能删除字符不能插入”那答案就变成n - 最长回文子序列长度如果改成“可以替换字符”又是完全不同的思路。这些变形题目在周赛里反复出现核心都是对回文串结构的理解。把1312吃透再做这些变体你会觉得轻松很多。