在面试和竞赛里翻来覆去考的往往不是那道题本身而是它背后的一整套思维方法。回文子串和回文子序列的DP问题就是典型中的典型题目看着简单甚至读一遍样例就能理解但真上手写状态、推转移、卡边界能卡住一大半人。刷这类题很多人只记住了“dp[i][j]表示从i到j是个回文串”却不知道为什么要这么设计更不知道这套东西能一路延伸到多少个看起来八竿子打不着的题目上去。这篇文章我想把回文子串、回文子序列以及一系列衍生DP问题串起来讲透。不只是讲结论重点说清楚每一步的“为什么”状态为什么这么定遍历顺序为什么是那样二维DP怎么滚成一维以及从回文问题引申出去所谓的“最长不上升子序列优化”“数位DP”“四边形不等式优化DP”“树形DP选课”“动态DP”到底和它有什么联系。不管你是刚学DP的新手还是想系统整理解题框架的选手都可以按着自己的需要跳着读。我会从最基础的回文子串讲起一路拉到进阶优化每一段都配实操级别的细节。1. 从一道经典题说起回文子串与子序列到底差在哪1.1 子串和子序列一字之差天壤之别很多人把“回文子串”和“回文子序列”当成一类题其实它们的解法思路完全不同区分不清是后面所有混乱的根源。子串substring要求连续。比如“abcba”里的“bcb”是子串但“aca”不是因为a和c在原串中不是紧挨着的。子序列subsequence只要求保持相对顺序不要求连续。所以“abcba”里“aca”就是子序列下标取1、3、5就行。这个区别直接决定了DP状态设计的方向。回文子串天然适合区间DP或中心扩展因为回文性是“从中间向两边扩散”的性质而回文子序列则因为可以跳过字符更接近“两端匹配、中间自由”的序列DP模型。我还见过不少人在做题时把两个概念混着用比如用中心扩展法去数回文子序列数到一半发现字符跳着匹配不上就卡住了。我的建议是拿到题先问自己一句话——“连续不连续”这个问题的答案直接决定你用哪套状态定义。1.2 为什么动态规划是这类题的标准解回文问题暴力做法很简单枚举所有子串或子序列判断是不是回文就行了。但复杂度毫无悬念地爆炸。一个长度为n的字符串子串数量是O(n^2)个每个判断一次O(n)的话整体O(n^3)对于几百上千的数据长度就得歇菜。子序列就更夸张了2^n种可能完全不可枚举。DP解决这个问题靠的是复用判断结果。一个串是回文有一个非常朴素的性质去掉首尾两个字符剩下中间的部分依然是回文。反过来讲如果中间部分是回文且新加的首尾字符相等那么扩展后的串也是回文。这个性质把“大问题”和“小问题”联系起来天然适合用DP去递推。所以任何回文类DP问题的第一步都是寻找这种“能通过子问题的状态拼出当前状态”的递推关系。找对了题就解决了一半找错了后面写再多代码也是在补漏洞。2. 回文子串区间DP的样板题2.1 状态设计与转移逻辑先定义一个最经典的题给你一个字符串s统计其中回文子串的个数。状态定义我用一个二维布尔数组dp[i][j]表示s[i]到s[j]这一段子串是否为回文串。之所以用布尔而不是直接计数是因为计数可以放到最后统一累加而中间的判断必须依赖“某个区间是否回文”这个布尔信息。转移方程分三种情况写i等于j单个字符必然是回文串j等于i1两个字符直接比较s[i]是否等于s[j]j大于i1需要同时满足s[i]等于s[j]并且dp[i1][j-1]为真。很多人卡在这一步二维DP的遍历顺序应该怎么写如果先枚举i再枚举j那算dp[i][j]时dp[i1][j-1]可能还没算出来结果就错了。正确做法是按区间长度从小到大枚举。先算长度为1和2的再算长度为3的以此类推。长度大的依赖长度小的顺序绝对不会乱。s abcba n len(s) dp [[False] * n for _ in range(n)] count 0 for length in range(1, n 1): for i in range(n - length 1): j i length - 1 if length 1: dp[i][j] True elif length 2: dp[i][j] (s[i] s[j]) else: dp[i][j] (s[i] s[j]) and dp[i 1][j - 1] if dp[i][j]: count 1这个代码是O(n^2)的时间、O(n^2)的空间。对大多数题目来说已经足够了。我还习惯把“按长度枚举”和“从后往前枚举i、从前往后枚举j”两种写法对照着看后者本质上也是在保证长度短的先算能加深理解。2.2 中心扩展与Manacher的定位区间DP最稳但它不是唯一的解法甚至不是最优的。中心扩展的思路是把每个位置或每两个位置之间的空档当作回文中心向两边扩散直到两边字符不等为止。这样做也是O(n^2)的时间但空间降到O(1)。如果你在笔试中写代码中心扩展往往写起来更快不容易在遍历顺序上翻车。我还建议大家在整理回文子串问题时知道还有一个Manacher算法的存在。它能在O(n)时间内解决最长回文子串问题而且代码量不算特别大。但要注意Manacher的适用面很窄它本质上是“线性求最长回文半径”的专用算法解决计数类问题需要变形DP和中心扩展则更通用。我的实操经验是竞赛里Manacher有它的舞台但工作面试中DP和中心扩展的优先级更高因为考官更想看你如何一步步设计状态而不是背一个模板。如果面试官进一步追问“能不能把空间压缩成一维”这就回到了区间DP的空间优化问题。其实dp[i][j]只依赖j-1这一列的信息可以用一维数组按列滚动但注意更新时要防止旧值被覆盖。这个细节我在后面第5章会专门讲。3. 最长回文子序列从“判断”到“计数”的进阶3.1 状态设计区间DP的子序列化变形回文子串是“连续”的所以判断区间两端相等后中间必须也回文区间长度变短是确定的。回文子序列允许跳过字符所以状态定义就变成了“长度”转移也变成了“取最大/求和”而不是“判断真或假”。最长回文子序列LPS的状态定义是我讲题时一定会重点强调的dp[i][j]表示字符串s[i..j]这一段中最长回文子序列的长度。初始时dp[i][i]等于1因为单个字符自己就是长度为1的回文子序列。转移分两种情况如果s[i]等于s[j]那么可以直接把两头都收进口袋里dp[i][j] dp[i1][j-1] 2如果s[i]不等于s[j]两头不能同时取只能丢掉其中一头取dp[i1][j]和dp[i][j-1]中较大的一个。写代码时遍历顺序依然是按区间长度从小到大。从结果上看答案是dp[0][n-1]。我还想额外说一件事如果想输出具体的回文子序列而不是只输出长度dp表不仅仅负责算长度它还可以用来回溯。比如从dp[0][n-1]出发如果s[i]等于s[j]那就记录这两个字符然后进入dp[i1][j-1]否则比较dp[i1][j]和dp[i][j-1]哪边大往哪边走。实际操作时用这个套路很快就能把结果构造出来比另开一个数组记路径更省事。3.2 回文子序列计数与“不同的子序列”的交叉与最长回文子序列看起来很像的是“统计一个字符串中回文子序列的个数”以及热词里提到的“不同的子序列”问题。这里我想把它们放一起说因为它们共享同一个状态模型稍加变化就是一道新题。统计回文子序列个数时dp[i][j]表示s[i..j]中回文子序列的数量。同样按s[i]是否等于s[j]分类若s[i]不等于s[j]那么s[i..j]内的回文子序列等于s[i1..j]加上s[i..j-1]但要减去重复计算的s[i1..j-1]部分。所以dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1]。若s[i]等于s[j]可以把它们放进每一个内部回文子序列的两端生成新的回文子序列。所以dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1] (两边都不取的情况会重复计入实际推导后可用简化公式dp[i][j] dp[i1][j-1] 1 只取一端的内层数量不同题解写法略有差异核心是理解会重复哪些部分)。这类计数DP最大的坑就是重复计数。很多人想当然地认为“两端相等就直接加”结果数出来的数量比暴力跑出来的还大。我推荐写完后一定要用一个小字符串比如“aaa”手动验算一遍长度为3时回文子序列应该有7个单字符3个双字符3个三字符1个。这个例子能暴露绝大多数公式错误。而“不同的子序列”是另一个经典计数DP求一个字符串s中有多少个不同的子序列等于t或者求s中互不相同的子序列总数。前者是二维DPdp[i][j]表示s前i个字符中匹配t前j个字符的方案数转移时考虑s[i]要不要参与匹配。后者则是一维DP加一个“上次出现位置”的数组用于去重。这些题与回文子序列计数共享的核心思想是计数DP里去重永远比累加更关键。你一旦理解了这个遇见任何带“不同”二字的DP题心里都有底。4. 跳出回文这些DP技巧其实是同一套思维4.1 最长不上升子序列的二分优化从“枚举决策”到“维护单调序列”热词里有一个高频搜索“最长不上升子序列优化”这个优化技巧和回文子序列看似无关但它们都指向一个事实序列DP的复杂度瓶颈往往在于“如何快速找到最优转移来源”。最长上升子序列LIS的经典做法是O(n^2)枚举每个位置i再枚举i之前的所有位置j如果a[j]小于a[i]就能把长度延长。但“最长不上升子序列”换个方向同样适用问题在于n一旦到了10万O(n^2)就完全扛不住了。优化的核心是换一种视角不再枚举“每个位置从哪里转移”而是维护一个数组d其中d[k]表示长度为k的不上升子序列的“最优结尾”。由于不上升我们要找的是第一个小于当前元素的d[k]然后把当前位置接到它后面。配合二分查找总复杂度降到O(n log n)。我为什么在讲回文DP时扯到LIS优化因为这两种题都在反复训练一个能力**当你发现朴素转移是O(n^3)或O(n^2)时能不能把“枚举所有可能转移点”改成“在某个有序结构里二分查一个最优转移点”**回文子串中心扩展后可以二分回文半径马拉车LIS优化用二分找插入位置本质上都是把“线性扫描”升级成“对数查找”。4.2 数位DP与回文数把“区间统计”变成“按位决策”“数位DP”也是热词里的高频项。把回文问题放到数位DP里会这样考统计[L, R]范围内有多少个数是回文数。数位DP的核心是按位决策、状态压缩。我们不用真的枚举每个数而是从最高位开始一位一位地选数字同时维护“前面选的数位是什么样的”。因为一个回文数的后半段必须和前半段对称所以我们在枚举前半段时就得把已经选的数位存起来方便后面比较。数位DP的状态有点像回文序列DP的“状态记忆”版pos表示当前处理到第几位start表示是否已经开始填数tight表示之前是否紧贴上界还有前面这些位的数字信息。记忆中很多初学者包括我自己刚学时最容易漏掉的参数就是tight。漏了它统计区间上界时数据就会悄悄地超出范围。数位DP写起来我强烈建议用记忆化搜索而不是纯递推。记忆化搜索的代码结构更像人脑的思路从高位往低位走每一层决定一个数字边界条件写在递归入口。尤其遇到多个限制条件叠加时搜索写法改状态参数容易得多纯递推的数组维度一旦漏了一个调半天都查不出来。4.3 四边形不等式优化、树形DP选课与动态DP的通用化延伸热词里还有“四边形不等式优化DP”“树形DP选课”“动态DP”这些名字看着高深但它们和回文DP有共同的底层逻辑当状态转移方程已经确定后能不能找到某种结构让最优决策点具有单调性从而跳过大量无效枚举。四边形不等式优化很好懂它适合一类区间DP。比如合并石子、最优二叉树这类题状态转移要枚举k把区间分成两半于是复杂度变成O(n^3)。如果你能证明代价函数满足四边形不等式那么dp[i][j]对应的最优分割点就会在dp[i][j-1]和dp[i1][j]的最优分割点之间枚举范围被压缩到常数级复杂度降到O(n^2)。这与回文子串的区间DP是同一个递推骨架只是多了“枚举分割点”这一步。“树形DP选课”则是把DP从线性结构搬到树上树上每个节点依赖父节点的选课状态经典的状态是dp[u][k]表示在u这棵子树上选k门课得到的最大收益。它与回文DP的差异在于遍历顺序变成了树形结构的后序遍历但“先处理完子问题、再用子问题拼父问题”的原则完全一致。树形DP看似难等你把“子问题”从“区间”换成“子树”后发现一切都很自然。“动态DP”DDP则更进一步它是把DP转移写成矩阵乘法再用线段树维护动态修改。回文问题虽然是静态字符串一旦允许修改字符那原本的二维DP就要配合数据结构去动态维护。这个方向已经是很进阶的内容但如果你的目标是竞赛拿高分值得了解一下“转移矩阵化”这个思路。4.4 线性DP与最大子序列你看不出它们是亲戚热词里还出现了“最大子序列”“动态规划线性DP”。最大子序列和Maximum Subarray可能是很多人学DP的第一个题它的状态定义只有一维dp[i]表示以第i个元素结尾的最大子数组和转移只需要dp[i]等于max(当前元素, dp[i-1]当前元素)。我特别喜欢拿这个题和回文子序列对比讲因为它们的“复杂度”差别极大最大子序列和一维状态O(n)时间O(1)空间最长回文子序列二维状态O(n^2)时间O(n^2)空间。但它们的思维起点一模一样保证状态能复用子结构信息。最大子序列和的子结构是“以前一个位置结尾的最大和”回文子序列的子结构是“更短区间的最大回文长度”。两者都是找一个“新增元素如何与已有最大状态结合”的公式。如果你碰见一道DP题完全没思路从这两个模型出发去套往往能找到一个方向。线性DP的特点就是状态只有一维遍历顺序简单区间DP的特点是状态有两维遍历顺序必须按区间长度来。把握住这个差异学习时就不会被各种题目表象带偏。5. 笔试面试中的常见问题与排查经验5.1 边界条件我最容易翻车的地方回文DP和区间DP的边界条件极其刁钻。常见的有单个字符的子串/子序列长度都是1不能想当然地初始化为0空串的子序列长度是0但空串是否算一个回文子序列题目往往会用“空串不计入答案”来限定要仔细读题长度为2的子串判断要单独写不能依赖dp[i1][j-1]因为它会变成dp[i1][i]语义成了空串处理不好就越界了。我一般会先写一个暴力版本拿小数据对拍再优化。暴力跑“aaa”“abba”“abcba”这些经典样例能很快发现边界错误。具体测试我推荐这样玩随便生成一个长度10以内的小串暴力枚举所有子序列判断回文和DP结果比对。用一个简单脚本就能做调试效率比肉眼检查高一个量级。5.2 空间优化滚动数组的“旧值覆盖”陷阱回文子串和最长回文子序列都能做滚动数组用一维数组替代二维表因为dp[i][j]只依赖dp[i1][j-1]、dp[i1][j]、dp[i][j-1]这几个位置。但滚动数组最怕的就是更新时把还没用到的旧值覆盖掉。比如用一维数组dp[j]表示当前i状态下、终点为j的结果计算时如果从左往右更新dp[j-1]已经被新值覆盖再去计算dp[j]时就会用到错误的状态。解决办法是从右往左更新让dp[j-1]仍然是上一轮的旧值。这个坑我在刷题早期反复踩。后来养成一个习惯每次上滚动数组前把二维的转移依赖图画一遍明确每个方向上的新旧值关系再决定遍历方向。5.3 状态表达式的直觉训练从题目答案倒推状态很多初学者最大的疑惑是“我看了题解写状态但自己拿到新题完全不知道状态怎么设。”我的经验是反向训练拿到别人的题解后先不看转移方程只看状态定义然后自己试着推导转移。推导不出来的地方再看一眼转移再反向问自己“为什么转移里会出现这个减法/这个max”这叫“倒推练习”比盲目刷题有用得多。做多了你会发现状态的设置无外乎回答几个问题题目的答案需要覆盖哪一段范围区间i和j前缀/后缀pos树节点编号决策的额外限制是什么剩余容量、已选数量、当前状态是否贴近上界哪些信息需要被记住才能支撑后续的转移回文的两端字符、LIS的当前结尾值、数位DP的tight标记真的把这几步想明白所谓的“动态规划线性DP”“区间DP”“数位DP”“树形DP”全都可以被归入同一个框架里。回文子串与子序列DP作为其中最经典也最直观的例子练熟这一套思路以后你再回头去看“四边形不等式优化”“动态DP”这类进阶内容会发现它们并不是天上掉下来的知识而只是同一个解题框架上不断生长的枝叶。这一点也是我写了这么多年DP题以后最想分享给后来者的一句话不是题海战术让人变强而是每一道题都把“状态设计”和“转移优化”这两件事看得更透一层。回文子串和子序列的题目恰好是练这个能力最顺手的一批题。希望上面这些经验能让你少走几步我当时走过的弯路。