回文串相关的动态规划题十道里有八道会卡在同一个地方你很快写出了转移方程看起来逻辑也对可一交上去就是超时。回头盯着代码看半天发现性能瓶颈根本不在主DP上而是每次判断“某个子串是不是回文”都要重新扫描一遍这个成本太隐形了平时练习不容易察觉一到在线评测就现原形。今天想聊的就是怎么根治这个“回文判断成本”。标题里“回文串dp | 预处理cost”其实点破了一类经典题型的通用解法先把所有子串的回文性算好存成一张二维表让后面的主DP直接用O(1)查询代替每次O(n)的扫描整体复杂度从O(n^3)直接压到O(n^2)。这套思路在分割回文串、最大回文子串、回文子序列、回文子串计数这几类题里都是通用地基理解了它很多题就不用再单独背模板了。我拿最典型的“分割回文串最少次数”来当主线把预处理这一步拆开揉碎讲清楚状态怎么设计、递推为什么成立、代码怎么写不会踩坑再把同样的预处理技巧迁移到其他几类回文DP里最后附一份调试时最容易翻车的排查清单。不管你是刚接触区间DP的新人还是刷题刷到有点麻木的老手这篇应该都能帮你把回文DP这条线彻底理顺。1. 先搞清楚这类题目到底在“考”什么先看一个非常经典的题目给你一个字符串 s要把它分割成若干个子串使每个子串都是回文串问最少分割次数。比如 aab切成 aa 和 b要切一刀答案是 1。第一次接触的人通常会想一个贪心思路从左往右尽量找最长的回文前缀。但马上就会发现这不对因为贪心只考虑了当前这一刀没有考虑这刀之后的影响。一个简单例子就能推翻它。所以这题的定性结论是单靠贪心不行必须考虑全局而这种“多阶段决策求最值”的问题天然就是动态规划的适用场景。那DP该怎么设最朴素的想法是设 dp[i] 表示前缀 s[0..i] 分割成回文子串需要的最少刀数。转移时枚举最后一刀的位置 j只要 s[j1..i] 是回文就有 dp[i] min(dp[i], dp[j] 1)。这看起来逻辑通顺但里面藏着一个隐性成本判断 s[j1..i] 是不是回文。如果每次转移都用双指针从两边往中间扫单次判断是O(n)枚举所有 j 又有一层循环整体就是O(n^3)。n 稍微上到几千这题基本就废了这正是大多数新手卡住的真正原因不是没想到DP而是没意识到回文判断的成本在拖后腿。解决的思路就是标题里说的“预处理cost”用O(n^2)的时间和空间提前把所有子串的回文性算成一张表让主DP里的每次判断都变成查表单次O(1)整体复杂度降一整个量级。这个思路其实特别好理解相当于你经常要回答“s[i..j]是不是回文”这个问题与其每次都临时算不如一次性把答案都准备在一张表里。预处理多花的时间在后续反复查询里能成倍赚回来。后面你会发现预处理不仅仅对分割题有效回文子串计数、最长回文子序列这些题本质上都共享同一张表。2. 怎么预处理这张回文表2.1 状态定义定义二维布尔数组 isPal[i][j]表示 s 从下标 i 到下标 j 这个子串是不是回文串。注意是闭区间所以 j i处理时只需要填矩阵的上三角下三角要么不填要么全部置为无效值。这个状态最重要的是它的递推关系。可以先想最长的子串怎么判断s[i..j] 是回文首先要求 s[i] s[j]其次要求去掉首尾之后s[i1..j-1] 也是回文。这就给出了递推式isPal[i][j] (s[i] s[j]) (j - i 2 || isPal[i1][j-1])这里的 j - i 2 对应长度小于等于3的子串长度1、2、3的子串只要两端字符相等就一定回文不需要依赖中间子串。长度1显然回文长度2相等就回文长度3中间只剩一个字符左右相等就回文。所以加一个短串的兜底条件递推边界就完整了。2.2 为什么必须按子串长度从小到大填这个递推关系看起来简洁真正写代码的时候绝大多数人第一个错就错在填表顺序上。isPal[i][j] 依赖 isPal[i1][j-1]也就是左下角那个位置。如果我们按 i 从 0 到 n-1、j 从 i 到 n-1 的顺序填去算 isPal[0][4] 的时候isPal[1][3] 可能还没算过。因为 i1 这一行还没被遍历到读到的就是初始值结果自然全错。正确的填法有几种最常见、最好理解的是按子串长度从小到大枚举。外层循环先定长度 len从 1 到 n内层循环枚举左端点 i右端点 j i len - 1。这样算 isPal[i][j] 时它依赖的长度是 len - 2已经在上一轮算好了查表拿到的必然是有效值。另一个思路是绕一下从右下往左上填。因为 isPal[i][j] 依赖的是更靠近左下的位置也就是 i 更大、j 更小的位置所以外层 i 从 n-1 往 0 走内层 j 从 i 往 n-1 走也能保证依赖先算好。这两种顺序说白了都是为了让依赖的方向可控我实际刷题时更习惯按长度枚举因为可以顺便处理 len1 和 len2 的初始化逻辑非常清晰。2.3 两种常用预处理方案对比上面说的区间递推是预处理回文表的第一种写法也是我推荐大家优先掌握的。还有另一种做法是中心扩展法每个位置以及每两个相邻字符之间的空隙作为回文中心向两边扩展边扩展边标记 isPal。它的效率同样是O(n^2)但写起来要分奇偶两种情况标记时也用不着递推式反而稍显啰嗦。我把两种方案列一张表对比一下维度区间递推法中心扩展法核心思路isPal[i][j] 由 isPal[i1][j-1] 推出每个中心向两边扩张能扩多远扩多远填表顺序按子串长度递增按中心位置逐个扩展奇偶处理不需要统一用长度判断奇数中心是单个字符偶数中心是相邻两字符代码量短嵌套循环干脆略长需要写两套扩展逻辑出错点填表顺序、边界条件中心下标、越界判断两种方法都解过很多题之后我的体会是中心扩展法在某些变体题里更直观比如要求输出最长回文子串本身时扩展过程中直接记录长度和起点但预处理这张表时区间递推法更不容易漏逻辑也好验证。下面统一用区间递推法讲。3. 用预处理后的表驱动主DP3.1 分割回文串主DP的状态与转移回到分割回文串这个题目。预处理出 isPal 之后主DP就变成一个很清爽的一维DP。设 dp[i] 表示前缀 s[0..i] 分割成全部回文子串所需的最少切割次数。初始化时直接把整个前缀 s[0..i] 当作一个整体如果它本身就是回文串那么分割次数就是 0不需要切任何一刀否则先设成一个极大值 INF等待枚举转移更新。转移时枚举最后一刀的位置 j满足 0 j i并且 s[j1..i] 是回文。这样在 s[j] 和 s[j1] 之间切一刀变成两个部分前缀 s[0..j] 已经由 dp[j] 给出了最优切割方案后面这一段是回文整体不再需要切。于是转移方程写成dp[i] min(dp[i], dp[j] 1)这个 1 就是中间那一刀。枚举所有可能的 j取最小值。你可能已经发现了这里枚举 j 的时候只是查了一下 isPal[j1][i]完全没有扫描字符串。这就是预处理的收益兑现点。整个主DP是O(n^2)预处理也是O(n^2)加起来还是O(n^2)相比一开始说的O(n^3)是本质的差别。3.2 完整可跑的代码示例下面这段代码用Python写逻辑步骤完整标注可以直接拿去跑几个用例验证感觉def min_cut(s: str) - int: n len(s) if n 0: return 0 # 1. 预处理回文表 is_pal [[False] * n for _ in range(n)] for length in range(1, n 1): # 按子串长度递增 for i in range(0, n - length 1): j i length - 1 if s[i] s[j]: if length 3: is_pal[i][j] True else: is_pal[i][j] is_pal[i 1][j - 1] # else: 保持 False # 2. 主DP最少切割次数 INF n # 最坏情况每个字符单独成段n-1刀 dp [INF] * n for i in range(n): if is_pal[0][i]: dp[i] 0 continue # 枚举最后一刀的位置 j 与 j1 之间 for j in range(i): if is_pal[j 1][i]: dp[i] min(dp[i], dp[j] 1) return dp[n - 1]跑个例子验证对 aab长度3。is_pal[0][0]True、is_pal[1][1]True、is_pal[2][2]True单字符。length2s[0]s[1]a所以 is_pal[0][1]Trueaa回文s[1]s[2]a!bis_pal[1][2]False。length3s[0]as[2]b不相等is_pal[0][2]False。主DPdp[0]0dp[1]is_pal[0][1]True所以 dp[1]0dp[2]is_pal[0][2]False枚举 j0is_pal[1][2]False不成立枚举 j1is_pal[2][2]Truedp[2]dp[1]11。最终答案是1刀正确。INF 初始值故意设成 n是因为最坏情况下每个字符单独一段需要的刀数也最多是 n-1n 一定够大。3.3 为什么要强调“整块是回文”这个约束有读者可能问为什么转移要条件判断 is_pal[j1][i] 为真不能直接无脑 dp[j]1因为缺少这个约束的话dp 就退化成普通的划分问题任何一刀都能切答案恒等于 n-1完全丢失了回文串这个限制。这个约束是整个DP的灵魂它把“分割成全部回文子串”的需求精确地翻译成了“每段都是回文”的判断条件。类似地如果题目改成“分割成一些子串使得每个子串都是回文串求最大能分成几段”转移只需要把 min 换成 max初始化方式变一下即可。你看理解了主DP的本质变体题就是小改动。4. 同一张回文表怎么迁移到其他回文DP题4.1 最长回文子序列DP的另一个分支回文子序列和回文子串有个字面上的区别子串要求连续子序列不要求连续。由于不要求连续这题的DP状态设计思路完全不同没法直接复用刚才的一维主DP它是一道标准的二维区间DP。设 dp[i][j] 表示 s[i..j] 中最长回文子序列的长度。根据两端字符是否相等可以写出下面的转移如果 s[i] s[j]那么可以把这两个字符挂在内部最长回文子序列的两端所以 dp[i][j] dp[i1][j-1] 2。如果 s[i] ! s[j]那它们不可能同时出现在一个回文子序列里只能在去掉其中一个端点里找最大值dp[i][j] max(dp[i1][j], dp[i][j-1])。边界i j 时 dp[i][j] 1i j 时 dp[i][j] 0。写代码时同样要注意填表顺序由于 dp[i][j] 依赖 dp[i1][j]、dp[i][j-1]、dp[i1][j-1]也就是左方向、下方向、左下方向三个位置所以要么 i 从大到小枚举、j 从小到大枚举要么直接按区间长度从短到长枚举。这个题目本身不依赖 isPal 表但它的预处理核心是另一张 dp 表处理技巧和回文串一样都是区间DP的填表顺序问题所以放一起讲。4.2 回文子串计数把判断变成记录次数如果要统计一个字符串里一共有多少个回文子串不同位置算不同子串经典的O(n^2)做法还是用 isPal 表。预处理之后把所有为真的位置直接加起来就行。空间可以优化成只保留数组但这里的主要收益依然是省掉了重复判断。比如统计 aaais_pal[0][0]、[1][1]、[2][2]、[0][1]、[1][2]、[0][2] 全是 True一共6个回文子串。如果不用预处理挨个判断每个子串复杂度级别会高很多尤其子串数量本身就接近O(n^2)重复扫描会让事情复杂化。相比之下马拉车算法能在线性时间内完成同样任务但那属于另一套技术路线。我的建议是先把 isPal 预处理用熟练应付中等难度的回文DP题足够深入竞赛需要追求极致性能的时候再补马拉车。4.3 回文DP的坐标遍历顺序总结把上面两类题串起来看回文串DP里凡是二维表填表顺序几乎都绕不开一个原则依赖的位置必须先算好。以 isPal 来说依赖左下角所以要么按长度从小到大要么 i 从大到小、j 从小到大以最长回文子序列的 dp 表来说依赖下方和左方所以也可以按长度从小到大枚举这样不管依赖哪个方向都保证已经算好啦。我总结的记忆方法是写这类区间DP之前先问问自己“这个格子依赖哪个方向的格子”再决定遍历方向。只要这一步想清楚代码不会因为顺序问题翻车。5. 常见问题与排查技巧实录5.1 一张表看清典型报错和坑现象根因解决办法结果比正确答案大填表顺序不对查到了未计算的 isPal导致误判为 False改按长度递增填表结果偏小忽略了长度2、3的兜底判断递推去查不存在的区间长度 3 直接置 True越界报错j 超出 n-1或 i1 / j-1 越界内层循环范围写成 n-length1答案总是 n-1主DP转移缺少回文条件判断检查 if is_pal[j1][i]循环变量搞混把 i、j 的意义理解反了写注释i 左端点、j 右端点字符串全是同字符结果不稳定取决于初始化确认 dp 初始化为 0 还是 INF先最典型的第一个坑展开说说字符串 abcbais_pal[0][4] 需要 is_pal[1][3]其实是bcb回文is_pal[1][3] 又需要 is_pal[2][2]c。按长度从小到大填先填长度1、长度2再填长度3、长度4最后填长度5每一步都踩在已计算的位置上这就是正确顺序的威力。第二个坑也很隐蔽有些代码在递推式里只写了is_pal[i][j] (s[i] s[j]) is_pal[i1][j-1]忘了处理 j-i 比较小的情况。对长度2的字符串i1 j-1此时访问 is_pal[1][0] 这种下三角未定义值轻则越界重则拿到脏数据。加入j - i 2作为直接判定条件后问题就消失了。第三类问题是主DP初始化的细节。有几版代码喜欢把 dp 整体初始化为一个 INF然后逐个更新这样也能用但更高效的写法是先判断整个前缀本身是不是回文是就直接赋值 0不需要进 inner 枚举。跑到大样例时这一步能省不少无用循环。5.2 空间优化的一个经典方向isPal 表是n^2的布尔数组内存占用上限大概每百万格一兆字节的量级n到5000时是25 MB左右大部分评测环境是安全的。但如果遇到 n 到10000级别空间就有点不够意思了此时可以把 isPal 从二维数组优化成二维布尔值的位压缩存储或者配合滚动数组只保留两行。不过要注意滚动数组虽然节省内存但会让代码的可读性下降尤其对新手来说不如先写完整二维表等AC了再考虑优化。这些优化在中等题目里一般用不到但知道原理能让你在真正的重型区间DP里多一个武器。5.3 一个高性价比的自测技巧回文DP的代码写完除了跑评测样例我习惯在自己电脑上写一组快速自测固定字符串 s手算出一个理论上明确的结果然后和程序输出对比。用几个典型回文串和几乎不包含回文的长串去测比盲目刷样例可能更有效。怎么确认代码没问题又不想完全依赖在线评测可以把程序跑小规模字符串暴力枚举出所有分割方案与DP结果逐一对比。n10 以下暴力很快这类对拍脚本是排查DP问题最可靠的帮手我几乎每次写区间DP都会用它验一遍。6. 我自己踩过几次坑之后的实操心得回文串DP这个专题核心就是“预处理cost”这四个字。一开始我写题时也喜欢上来就干主DP觉得预处理是额外步骤浪费时间结果一次次在超时中浪费更久。后来彻底养成了习惯凡是涉及多次回文判断的题目先停下来想一想能不能用一张表把所有回文判断O(1)化再写主逻辑。这个思维转换之后回文串相关的题从最害怕的考点变成了送分题。另外还有一个弹簧式的小技巧如果一道回文DP题要求输“最小切割次数”但你又担心自己的预处理表格写错可以先只跑样本量很小的测试甚至自己手推一遍 isPal 表看几个关键位置是否正确。比如全等字符这个极端情况isPal 表应当所有格子都为 True这可以作为形式化验证的第一步。全不相同字符的字符串只允许单字符为 True这两个极端例子的检查成本极低却能挡住一大半逻辑错误。最后如果真的进入竞赛或者面试环境想用空间换时间还要注意代码的常数优化把二维数组的下标访问尽量内存局部化按行的方式去遍历把 Python 里容易超时的循环尽量用列表推导或者预处理外层数据来压缩。核心步骤用 isPal 表查询保证每个判断都是常数时间整体下来就算遇到 n2000 的字符串一般也能稳过。