1. 从一道面试题说起回文串为什么是动态规划的黄金训练场刷算法题的人多少都有这种感觉有的知识点是“看了就会写了就废”动态规划绝对排得上号。而动态规划里面有一类题目又特别适合用来建立DP手感那就是回文串系列。回文串的定义很简单一个字符串从前往后读和从后往前读完全一样比如aabaa、civic甚至单个字符a也算回文串。判断很简单但一旦加上“计数”“最长”“最少分割”“最少插入”这些优化目标难度立刻就上来了。这类题目在面试中出现的频率极高尤其是大厂笔试和算法面试的中等偏上难度题几乎每年都能看到它们的变体。这一篇要讲的六道题正好串起了回文串问题的完整脉络回文子串计数最长回文子串求具体子串分割回文串 IV可行性判断分割回文串 II最少分割次数最长回文子序列子序列版本让字符串成为回文串的最少插入次数这六道题不是孤立存在的它们共享同一套核心工具——回文串预处理表然后在上面做不同的动态规划决策。把这六道题放在一起刷一遍下来你对“区间DP”“状态定义”“子串与子序列的区别”这些东西会有一个质的提升。这篇文章适合谁正在备战算法面试的人、刷LeetCode处于瓶颈期的人、以及上一轮设计数据的人。我会把每道题的思路、状态定义、转移方程、代码模板、以及我实际操作中踩过的坑全部写出来。你可以把它当成一份“可以直接抄作业”的专题笔记也可以当成梳理知识体系的参考资料。2. 先解决一个核心问题如何高效判断任意子串是不是回文串所有回文串题目的地基都是“快速判断某个子串是否为回文串”。你别小看这个操作很多题你感觉有思路但写不出来卡住的往往就是这一步。2.1 暴力判断为什么不行最直觉的办法是写一个辅助函数isPalindrome(s, i, j)不停用双指针从两边往中间扫。单次判断是O(n)的如果在动态规划过程中反复调用整体复杂度很容易飙到O(n³)。拿第三十七题来说如果每次切分都要重新判断子串是否回文数据规模稍微大一点就直接超时。所以我的习惯是凡是看到“回文子串”相关的题目第一步先预处理出一张二维布尔表dp[i][j]表示s[i..j]是否为回文串。后续所有判断都变成查表O(1)搞定。2.2 回文串预处理表的递推逻辑这张表的构建原理不复杂核心就一句话s[i..j]是回文串当且仅当s[i] s[j]且s[i1..j-1]也是回文串。翻译成代码bool[,] isPal new bool[n, n]; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j]) { if (j - i 1) isPal[i, j] true; else isPal[i, j] isPal[i 1, j - 1]; } } }这里有两个关键点值得展开说一下。第一个是遍历顺序。i必须从大到小j必须从小到大。因为计算isPal[i][j]依赖的是isPal[i1][j-1]i1比i大j-1比j小。如果你按照正常的i从小到大、j从大到小的顺序去遍历会用到还没计算出来的数据结果全错。这个坑我早期刷题时踩过好几次后来总结出一个规律——区间DP的遍历顺序永远盯着状态转移方程里依赖的方向。第二个是初始化条件。j - i 1实际上涵盖了两种情况单个字符j i和空串或相邻两个相同字符的情况j i 1。单个字符必然是回文这个没话说。长度为2的子串只要两个字符相等就是回文比如aa是回文ab不是所以不需要再往下递归。j - i 1时如果两个字符相等直接为true这也是base case的一部分。用这张表之后任意区间是否回文的查询都是O(1)这就是后面所有题目的基础。3. 六道经典题目逐一拆解从计数到分割的递进之路这六道题的顺序其实暗藏玄机。我按自己的刷题体验把它们分成了三个层次第一层是直接用回文表就能解决的计数和最长子串问题第二层是需要在回文表之上再做一次决策的分割问题第三层是跳出“连续子串”限制进入子序列和构造型问题。3.1 第35题回文子串的计数技巧题目要求统计一个字符串中所有回文子串的数量。注意这里统计的是子串需要连续而且每个位置不同的子串要分别计数。比如abc里每个字符单独算一个回文子串所以答案是3aaa则有a三个位置、aa两个位置、aaa一个位置共6个。用预处理表来做就非常直接了遍历所有i j的区间如果isPal[i][j]为真就累加计数。int countSubstrings(string s) { int n s.Length, ans 0; bool[,] isPal new bool[n, n]; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j] (j - i 1 || isPal[i 1, j - 1])) { isPal[i, j] true; ans; } } } return ans; }这里有一个细节就是判断条件里把j - i 1 || isPal[i1, j-1]直接合并在一起写利用了逻辑运算符的短路特性。当j - i 1时后面的isPal[i1, j-1]根本不会被执行所以不用担心数组越界问题。这个写法比单独写if判断更简洁也是我自己喜欢用的风格。如果你追求更高阶的解法可以了解中心扩展法和Manacher算法。中心扩展的思路是以每个字符或每两个字符之间的间隙为中心向两边扩展遇到相同字符就继续否则停止。Manacher算法利用了回文串的对称性把时间复杂度降到了O(n)但实现起来比较绕面试时能写出预处理表版本已经足够。3.2 第36题从计数到定位最长回文子串的区间DP写法这道题要求返回最长的回文子串本身不是长度。有两种主流做法中心扩展法和动态规划。中心扩展法写起来更快但既然我们这一篇的主题是DP重点看DP怎么做。在预处理表的基础上额外维护两个变量start和maxLen每次遇到isPal[i][j]为真且长度大于当前最大值时更新这两个记录。string LongestPalindrome(string s) { int n s.Length; bool[,] isPal new bool[n, n]; int start 0, maxLen 1; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j] (j - i 1 || isPal[i 1, j - 1])) { isPal[i, j] true; if (j - i 1 maxLen) { maxLen j - i 1; start i; } } } } return s.Substring(start, maxLen); }注意maxLen初始化为1因为任意单个字符都是回文串。如果你初始化为0那么当字符串非空时第一次更新也能正确工作但start初始位置如果是0当最长回文串长度为1时可能返回空字符串或位置不对所以稳妥起见还是初始化成1让默认答案落在第一个字符上。很多人在这一题上容易犯的一个错误是试图在DP填表的同时记录回文串内容本身写成一堆字符串截取操作性能又差逻辑又乱。正确的做法是只记录位置信息最后统一截取一次不要频繁做子串截取。3.3 第37题分割回文串 IV判断能否分成三个回文段这道题是分割系列的入门题问整个字符串能否被分成三个非空子串且每个子串都是回文串。有了预处理表这题就变成一个三重循环枚举分割点的问题。i表示第一段的结束位置j表示第二段的结束位置第三段自然就是[j1, n-1]。bool CheckPartitioning(string s) { int n s.Length; bool[,] isPal GeneratePalindromeTable(s); for (int i 0; i n - 2; i) { for (int j i 1; j n - 1; j) { if (isPal[0, i] isPal[i 1, j] isPal[j 1, n - 1]) return true; } } return false; }两层循环的时间复杂度是O(n²)配合O(1)的查表判断整体也就是O(n²)。我自己在写这道题的时候最开始想当然用了三层循环枚举三个分割点后来发现完全没有必要——第三段的分割位置可以由前两段的结束位置唯一确定。任何题目里都能看到“枚举范围能不能收缩”这个问题能少一层循环就少一层。这题还有一个细节i的范围是0到n-3因为第二段和第三段至少各占一个字符j从i1到n-2也保证了最后一段非空。这种边界条件的把控是区间DP题里最容易出错的地方。3.4 第38题分割回文串 II从可行性到最小分割次数第三十七题问“能不能分成三段”第三十八题就问“最少要切几刀才能让每一段都是回文”。这是经典的“前缀划分型DP”。状态定义是这道题的重中之重dp[i]表示前缀s[0..i]的最小分割次数。转移的思路是枚举最后一段的起点j如果s[j..i]是回文串那么s[0..i]的分割次数就是dp[j-1] 1取所有方案的最小值。int MinCut(string s) { int n s.Length; bool[,] isPal GeneratePalindromeTable(s); int[] dp new int[n]; for (int i 1; i n; i) dp[i] i; // 最坏情况每个字符切一刀 for (int i 1; i n; i) { if (isPal[0, i]) { dp[i] 0; continue; } for (int j 1; j i; j) { if (isPal[j, i]) dp[i] Math.Min(dp[i], dp[j - 1] 1); } } return dp[n - 1]; }这里有一个很重要的优化动作当整个前缀本身已经是回文串时直接令dp[i] 0不需要再进内层循环。这个判断能节省不少时间因为在实际测试数据中完全回文的前缀并不少见。dp数组初始化为dp[i] i的逻辑也很直观一个长度为i1的字符串最极端的情况就是每个字符单独成段需要切i刀。这样初始化就保证了动态规划求解过程中第一轮比较一定能得到一个上限值。这道题是六道题里我自己觉得最需要“先想清楚状态再动手”的一道。如果你上来就想着“用二维区间DP直接求整个串的分割次数”很容易陷入一个误区dp[i][j]表示子串s[i..j]的最少分割次数这样定义不是不行但是状态数量是O(n²)转移还要枚举分割点复杂度直接成了O(n³)。而用一维前缀DP状态数量变成O(n)转移复杂度仍然是O(n)整体就是O(n²)这才是最优姿态。3.5 第39题最长回文子序列从“连续”到“不连续”的思维转变前面几道题处理的都是子串要求连续。从这道题开始进入子序列的范围不再要求连续只要求保持原有顺序。比如bbbab的最长回文子序列是bbbb长度4但没有任何一个长度为4的回文子串。这题的状态定义和之前的完全不一样了。用dp[i][j]表示子串s[i..j]中的最长回文子序列长度。当s[i] s[j]时这两个字符可以同时进入回文子序列所以dp[i][j] dp[i1][j-1] 2当两端字符不同时只能舍弃一端取max(dp[i1][j], dp[i][j-1])。int LongestPalindromeSubseq(string s) { int n s.Length; int[,] dp new int[n, n]; for (int i n - 1; i 0; i--) { dp[i, i] 1; for (int j i 1; j n; j) { if (s[i] s[j]) dp[i, j] dp[i 1, j - 1] 2; else dp[i, j] Math.Max(dp[i 1, j], dp[i, j - 1]); } } return dp[0, n - 1]; }这里需要注意一个细节当j i 1且s[i] s[j]时会访问dp[i1][j-1]也就是dp[i1][i]这个位置不在我们常规计算的范围内。但因为dp数组默认值是0所以它恰好代表“空串的回文子序列长度为0”逻辑上是自洽的不需要额外特殊处理。这就是“数组初始化的默认值有时候刚好是我们要的base case”的例子。另一个理解这道题的思路是把它转化成LCS问题将原字符串反转求原字符串和反转字符串的最长公共子序列长度就是最长回文子序列的长度。这个方法的正确性来源于回文串的特点一个回文子序列在反转后的字符串里依然以相同的相对顺序出现。两种写法都能通过但区间DP版本更通用一些因为后续的最少插入次数就是从它演变过来的。3.6 第40题成为回文串的最少插入次数一种逆向思维的胜利这道题问的是在一个字符串中任意位置插入任意字符最少插入多少个字符能让它变成一个回文串。有个很巧妙的结论答案等于字符串长度减去最长回文子序列的长度。为什么呢因为原字符串中的最长回文子序列已经天然对称了剩下的字符只要在合适的位置插入一个对称副本就能补全回文每插入一个字符就消除一个“不对称”的字符所以最少插入次数就是非回文子序列的字符数量。int MinInsertions(string s) { int n s.Length; int[,] dp new int[n, n]; for (int i n - 1; i 0; i--) { dp[i, i] 1; for (int j i 1; j n; j) { if (s[i] s[j]) dp[i, j] dp[i 1, j - 1] 2; else dp[i, j] Math.Max(dp[i 1, j], dp[i, j - 1]); } } return n - dp[0, n - 1]; }从代码上来看这道题和上一题的DP表构建几乎一样唯一多出来的就是最后return n - dp[0, n-1]这一步。这道题如果你不知道这个结论直接去贪心地配对字符很容易陷入“改了这边那边又不对”的困境。我在面试中也被问过这道题面试官当时追问了一个变体如果不仅要求插入次数最少还要求输出最终的回文串怎么办这就需要在DP之外额外维护一个“从哪里转移来”的路径信息或者用双指针构造法来解决。这类变体可以留到掌握了基础版本之后再去深入。4. 从一道题到一类题回文串问题的通用状态设计与模板提炼刷完这六道题你可能会发现它们之间的关联非常紧密。这六道题共享一个核心工具回文串预处理表但在DP状态的设计上各有侧重。把它们放在一起对比才能看清“回文串类动态规划”的全貌。4.1 两种典型的回文DP状态形态回文串题目中的DP状态大致可以分成两类区间型DP和前缀型DP。区间型DP的状态是dp[i][j]直接描述“子串s[i..j]上的某个最优值或布尔值”通常用于最长回文子序列、最少插入次数这类问题。它的特点是状态维度是二维的转移时关注区间长度的收缩和扩展。前缀型DP的状态是dp[i]描述“前缀s[0..i]的某个最优值或方案数”通常用于分割类问题比如回文分割、单词拆分。这类问题的关键在于转移时枚举“最后一段”的起点把大问题拆解成更小的前缀问题。聪明的做法是看到题目先判断它问的是“子串/子序列本身的性质”还是“在子串上做划分/组合”前者大概率用区间型后者大概率用前缀型。这两类状态的思维模式不同混用的话很容易写出一个“看起来对但就是跑不对”的代码。4.2 回文串题目的标准操作流水线我把这两类DP状态的共性与技巧做了个总结形成了自己的刷题模板分享给你第一步确定字符串下标语义。建议统一用i表示左边界、j表示右边界区间用左闭右闭[i, j]避免左闭右开带来的一堆1、-1的边界计算。第二步画出状态转移图。不管是什么DP先把“当前状态依赖哪些子状态”写清楚再决定遍历顺序。回文串区间DP几乎都是从小区间推大区间所以外层循环从后往前、内层从前往后是标配。第三步写好base case。单个字符的情况、长度为2的情况、空串的情况这三种边界是回文串题目出错的重灾区。建议在写代码前先手推一个长度为3的例子比如aba和abc确认转移方程和边界条件都能正常工作。第四步验证时间和空间。回文串DP的复杂度绝大多数是O(n²)空间可以优化成一维甚至滚动数组。如果写出来是O(n³)先想一下是不是枚举了不必要的分割点或者做了重复计算。4.3 空间优化的思路从二维到一维的秘密拿第三十九题最长回文子序列来说dp[i][j]依赖于dp[i1][j-1]、dp[i1][j]和dp[i][j-1]。如果仔细观察dp[i]这一行只依赖下一行dp[i1]和当前行左边的位置所以我们实际上可以用一维数组加一个临时变量来做空间压缩。一行一行的滚动更新因为dp[i1][j-1]对应到一维数组中就是“上一次外层循环遗留的左邻位置”如果不提前保存内层循环一更新就被覆盖了。这就是为什么空间压缩需要额外的临时变量prev来记录旧值。int LongestPalindromeSubseqOptimized(string s) { int n s.Length; int[] dp new int[n]; for (int i n - 1; i 0; i--) { dp[i] 1; int prev 0; for (int j i 1; j n; j) { int temp dp[j]; if (s[i] s[j]) dp[j] prev 2; else dp[j] Math.Max(dp[j], dp[j - 1]); prev temp; } } return dp[n - 1]; }这一段代码初看不太好懂它是很多初学者“好像看懂了但自己写不出来”的典型。关键在于理解prev保存的是什么它保存的是本轮j循环更新前dp[j-1]在上上轮也就是i1那一行的值。prev的初始值是0正好对应dp[i1][i]空串的回文子序列长度跟第一版代码里数组默认值起的作用完全一致。空间优化在面试中不是第一优先级但如果你在写题过程中能顺手做出来绝对是加分的。笔试和面试中经常要求“优化空间复杂度”这个版本可以作为进阶答案。5. 常见问题与排查技巧实录我在刷这六道题时踩过的坑这一部分我把自己实际刷题过程中遇到过的问题整理成了一份避坑清单都是血泪教训。5.1 遍历方向给整反了结果答案全错这是我早期最常犯的错误。区间DP的遍历方向不是由i和j的大小关系决定的而是由状态转移方程里依赖的方向决定的。比如dp[i][j]依赖dp[i1][j-1]那么在计算dp[i][j]的时候i1那行必须已经算完所以外层i要从大到小。判断方法很简单看转移方程画一个二维表格把每个格子计算时需要读取的其他格子标出来然后沿着“先算被依赖的格子”的方向遍历。不要死记“从右下到左上”之类的口诀因为不同题目的依赖方向不完全一样。5.2 子串和子序列的概念混淆第三十六题和第三十九题的差别就在连续与不连续上。子串版的判断条件isPal[i1][j-1]要求中间部分也必须是回文子序列版的转移却允许舍弃两端的字符只取max。如果你把这两个的思维混在一起很容易写出“既不连续也不最优”的四不像代码。我自己的记忆方式是子串问题里两端的字符如果相等中间的区间必须整体满足某种性质子序列问题里两端字符可以不匹配分别考虑丢左边还是丢右边。5.3 初始化base case的边界条件不完整单个字符dp[i][i] 1长度为2的区间要能直接判断长度大于2的往下递归。这三个层次在代码里都有体现。如果你初始化时只设置了dp[i][i] 1第二天刷题时会发现有些长度为2的区间在递归时访问到了奇怪的区域。最稳妥的方式是写一个长度为2和长度为3的小测试用例在提交前手动跑一遍。比如aa和aba这两个用例基本能覆盖所有常见边界。5.4 分割类问题的“最坏情况初始值”设得太小在第三十八题里如果dp[i]初始化成一个大数或者int.MaxValue取最小值Math.Min的时候没问题如果初始化成0那所有转移都会把0当作最优解保留下来答案永远不对。初始化的思路应该遵循“最坏情况下的可行解”而不是“正无穷”。在只要求分割次数的题里dp[i] i是最自然的初值如果题目要求拐弯抹角分“最多能分多少段”初值才需要改成0。永远先想清楚数组里存的是“最大值”还是“最小值”再决定初始化的方向。5.5 优化技巧把回文表判断单独封装成函数刷完整套题之后你会发现所有题目里都会反复用到“判断一个子串是否为回文”。我的建议是把生成回文表的逻辑单独封装成一个函数至少在本地刷题时这样做避免每道题都复制粘贴一大坨表生成代码而且不容易因为改了一处忘记另一处而出错。bool[,] GeneratePalindromeTable(string s) { int n s.Length; bool[,] dp new bool[n, n]; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j] (j - i 1 || dp[i 1, j - 1])) dp[i, j] true; } } return dp; }6. 六道题的能力图谱与实战建议按我自己的理解这六道题在面试中的考察层级各不相同。把它们放在一张表里对比你就能看得非常清楚题目核心考点状态类型时间复杂度面试出现频率35.回文子串预处理表、计数二维布尔表O(n²)高36.最长回文子串区间DP或中心扩展二维布尔表位置记录O(n²)极高37.分割回文串 IV枚举分割点、可行性二维布尔表O(n²)中38.分割回文串 II前缀DP、最小值一维前缀DPO(n²)高39.最长回文子序列区间DP、子序列概念二维区间DPO(n²)极高40.最少插入次数子序列结论变体二维区间DPO(n²)中高从这张表能看出一个规律回文串问题的核心本质其实就是两件事。第一件事是“判断回文”用预处理表统一解决第二件事是“利用回文信息做决策”根据问题类型选择区间DP或前缀DP。两道核心题36和39代表了两种不同的DP思考方式另外四道都是在它们基础上加了特定条件或者做了变化。如果你准备面试我建议把36、38、39这三道题按顺序刷透。第36题练的是“预处理表区间遍历”第38题练的是“前缀分割DP”第39题练的是“区间DP的经典转移”。这三道题覆盖了回文串动态规划的绝大多数考点其余的几道题你可以在三题之后作为强化训练。7. 给不同基础读者的刷题路径建议如果你刚接触动态规划没多久建议不要直接上第40题那道题虽然代码短但背后的结论推导需要一定基础。推荐的顺序是从第35题开始它只需要做判断和计数是理解回文表构建过程最直接的方式。紧接着做第36题把“回文表记录位置”这套组合拳打熟中间可以对比中心扩展法的差异加深理解。如果你已经刷过一些DP可以直接从第38题和第39题开始。第38题的前缀DP状态定义在后续很多字符串问题里都有应用第39题的区间DP转移方程也是很多高级题目的基础模块。第37题和第40题适合作为查漏补缺的练习题第37题很直观第40题需要你记住“最长回文子序列与最少插入次数”的关系。如果面试中遇到这道题能快速反应出这个转化关系就已经成功了一半。复习的时候建议把这六道题当成一个整体来回顾。只看题目名字自己在脑海里过一遍状态定义和转移方程然后默写代码。如果有一道题卡住了就回到对应的章节对照着看。这种“整体记忆法”比单独记每道题要高效得多因为题目之间的联系本身就是最好的记忆锚点。