回文串DP优化：预处理cost把O(n³)压到O(n²)的通用解法

回文串相关的动态规划题，十道里有八道会卡在同一个地方：你很快写出了转移方程，看起来逻辑也对，可一交上去就是超时。回头盯着代码看半天，发现性能瓶颈根本不在主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[j+1..i] 是回文，就有 dp[i] = min(dp[i], dp[j] + 1)。这看起来逻辑通顺，但里面藏着一个隐性成本：判断 s[j+1..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[i+1..j-1] 也是回文。这就给出了递推式：

isPal[i][j] = (s[i] == s[j]) && (j - i <= 2 || isPal[i+1][j-1])

这里的 j - i <= 2 对应长度小于等于3的子串：长度1、2、3的子串，只要两端字符相等，就一定回文，不需要依赖中间子串。长度1显然回文；长度2相等就回文；长度3中间只剩一个字符，左右相等就回文。所以加一个短串的兜底条件，递推边界就完整了。

2.2 为什么必须按子串长度从小到大填

这个递推关系看起来简洁，真正写代码的时候，绝大多数人第一个错就错在填表顺序上。

isPal[i][j] 依赖 isPal[i+1][j-1]，也就是左下角那个位置。如果我们按 i 从 0 到 n-1、j 从 i 到 n-1 的顺序填，去算 isPal[0][4] 的时候，isPal[1][3] 可能还没算过。因为 i=1 这一行还没被遍历到，读到的就是初始值，结果自然全错。

正确的填法有几种，最常见、最好理解的是：按子串长度从小到大枚举。外层循环先定长度 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 走，也能保证依赖先算好。这两种顺序说白了都是为了让依赖的方向可控，我实际刷题时更习惯按长度枚举，因为可以顺便处理 len=1 和 len=2 的初始化，逻辑非常清晰。

2.3 两种常用预处理方案对比

上面说的区间递推是预处理回文表的第一种写法，也是我推荐大家优先掌握的。还有另一种做法是中心扩展法：每个位置（以及每两个相邻字符之间的空隙）作为回文中心，向两边扩展，边扩展边标记 isPal。它的效率同样是O(n^2)，但写起来要分奇偶两种情况，标记时也用不着递推式，反而稍显啰嗦。

我把两种方案列一张表对比一下：

两种方法都解过很多题之后，我的体会是：中心扩展法在某些变体题里更直观（比如要求输出最长回文子串本身时，扩展过程中直接记录长度和起点），但预处理这张表时，区间递推法更不容易漏，逻辑也好验证。下面统一用区间递推法讲。

3. 用预处理后的表驱动主DP

3.1 分割回文串：主DP的状态与转移

回到分割回文串这个题目。预处理出 isPal 之后，主DP就变成一个很清爽的一维DP。

设 dp[i] 表示前缀 s[0..i] 分割成全部回文子串所需的最少切割次数。初始化时，直接把整个前缀 s[0..i] 当作一个整体，如果它本身就是回文串，那么分割次数就是 0，不需要切任何一刀；否则先设成一个极大值 INF，等待枚举转移更新。

转移时枚举最后一刀的位置 j，满足 0 <= j < i，并且 s[j+1..i] 是回文。这样在 s[j] 和 s[j+1] 之间切一刀，变成两个部分：前缀 s[0..j] 已经由 dp[j] 给出了最优切割方案，后面这一段是回文整体，不再需要切。于是转移方程写成：

dp[i] = min(dp[i], dp[j] + 1)

这个 +1 就是中间那一刀。枚举所有可能的 j，取最小值。

你可能已经发现了，这里枚举 j 的时候，只是查了一下 isPal[j+1][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 与 j+1 之间 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（单字符）。
• length=2：s[0]==s[1]='a'，所以 is_pal[0][1]=True（"aa"回文）；s[1]==s[2]，'a'!='b'，is_pal[1][2]=False。
• length=3：s[0]='a'，s[2]='b'，不相等，is_pal[0][2]=False。

主DP：dp[0]=0；dp[1]：is_pal[0][1]=True，所以 dp[1]=0；dp[2]：is_pal[0][2]=False，枚举 j=0，is_pal[1][2]=False，不成立；枚举 j=1，is_pal[2][2]=True，dp[2]=dp[1]+1=1。最终答案是1刀，正确。

INF 初始值故意设成 n，是因为最坏情况下每个字符单独一段，需要的刀数也最多是 n-1，n 一定够大。

3.3 为什么要强调“整块是回文”这个约束

有读者可能问：为什么转移要条件判断 is_pal[j+1][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[i+1][j-1] + 2。
• 如果 s[i] != s[j]，那它们不可能同时出现在一个回文子序列里，只能在去掉其中一个端点里找最大值，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
• 边界：i == j 时 dp[i][j] = 1；i > j 时 dp[i][j] = 0。

写代码时同样要注意填表顺序，由于 dp[i][j] 依赖 dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1]，也就是左方向、下方向、左下方向三个位置，所以要么 i 从大到小枚举、j 从小到大枚举，要么直接按区间长度从短到长枚举。这个题目本身不依赖 isPal 表，但它的预处理核心是另一张 dp 表，处理技巧和回文串一样，都是区间DP的填表顺序问题，所以放一起讲。

4.2 回文子串计数：把判断变成记录次数

如果要统计一个字符串里一共有多少个回文子串（不同位置算不同子串），经典的O(n^2)做法还是用 isPal 表。预处理之后，把所有为真的位置直接加起来就行。空间可以优化成只保留数组，但这里的主要收益依然是省掉了重复判断。

比如统计 "aaa"：is_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 一张表看清典型报错和坑

先最典型的第一个坑展开说说：字符串 "abcba"，is_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[i+1][j-1]，忘了处理 j-i 比较小的情况。对长度2的字符串，i+1 > 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结果逐一对比。n=10 以下暴力很快，这类对拍脚本是排查DP问题最可靠的帮手，我几乎每次写区间DP都会用它验一遍。

6. 我自己踩过几次坑之后的实操心得

回文串DP这个专题，核心就是“预处理cost”这四个字。一开始我写题时也喜欢上来就干主DP，觉得预处理是额外步骤，浪费时间，结果一次次在超时中浪费更久。后来彻底养成了习惯：凡是涉及多次回文判断的题目，先停下来想一想，能不能用一张表把所有回文判断O(1)化，再写主逻辑。这个思维转换之后，回文串相关的题从最害怕的考点变成了送分题。

另外还有一个弹簧式的小技巧：如果一道回文DP题要求输“最小切割次数”，但你又担心自己的预处理表格写错，可以先只跑样本量很小的测试，甚至自己手推一遍 isPal 表，看几个关键位置是否正确。比如全等字符这个极端情况，isPal 表应当所有格子都为 True，这可以作为形式化验证的第一步。全不相同字符的字符串，只允许单字符为 True，这两个极端例子的检查成本极低，却能挡住一大半逻辑错误。

最后，如果真的进入竞赛或者面试环境想用空间换时间，还要注意代码的常数优化：把二维数组的下标访问尽量内存局部化，按行的方式去遍历；把 Python 里容易超时的循环尽量用列表推导或者预处理外层数据来压缩。核心步骤用 isPal 表查询，保证每个判断都是常数时间，整体下来，就算遇到 n=2000 的字符串，一般也能稳过。