动态规划实战：回文子串与最长回文子序列的区间DP解法

1. 先搞清楚题目到底在问什么别急着写代码做动态规划专题做到第四十五天最大的感受是题目难度不一定和数据规模成正比真正让人卡住的往往是“题目本身要求什么”这件事没想明白。647和516这两道题名字长得像解法也都在同一个dp框架里但一个是判断存在性一个是计算最优长度思维路径完全不同。1.1 回文子串统计的是连续片段的数量647题输入一个字符串s输出回文子串的个数。注意这里的“子串”必须是连续的。比如sabc那么子串只有a、b、c、ab、bc、abc这六种其中回文的是三个单字符答案就是3。这个“连续”是理解整道题的关键。因为要求连续你才能用一个区间[i, j]去表示一个子串也才能用“掐头去尾”的方式来递推判断回文。如果换成了子序列连续这个约束没了整个状态定义都得换那就是516题的事了。我还记得第一次做这题时想着能不能用前缀hash加二分去统计后来发现虽然能过但思路很绕而且边界条件一大堆。刷算法营到这个阶段其实最该练的是“看到题目的特征能快速映射到对应的算法套路”。回文子串的连续区间特征天然对应二维区间DP或者中心扩展这才是第一反应应该有的东西。1.2 最长回文子序列允许跳着选字符只求最大长度516题要求从字符串s中选出一个子序列使它是回文的并且长度最长。子序列不要求连续只要相对顺序不变就行。比如sbbbab答案不是bbb这种连续片段而是bbbb因为你可以跳着取下标0、1、3、4拼成四个b。这里一定要扭转之前做“子串”题目留下的惯性没必要要求你选中的字符在原字符串里挨在一起。这也意味着判断区间[i, j]内的最优回文子序列时即使s[i]和s[j]不相等你仍然有机会通过丢弃其中某一个字符来保留更优解。这种“丢弃一端继续找”的思路是516题和647题最本质的差异。所以先花五分钟在草稿纸上把这两个公式写出来647在判断“以i开头j结尾的这段连续字符是不是回文”答案是布尔值。516在求解“从i到j这段范围内最多能挑出多长的回文子序列”答案是长度。定了这个基调后面所有dp数组、转移方程、初始化的设计都会顺很多。2. 暴力枚举的成本到底有多高为什么必须动态规划每次写动态规划题我都会先估算一下暴力解法的时间复杂度不是为了证明暴力不可用而是为了让自己理解dp究竟优化掉了什么。这两道题放在一起看特别合适因为它们暴力解法的瓶颈各不相同。2.1 统计回文子串枚举区间加逐位校验最直观的暴力做法是双重循环枚举所有子串的起点i和终点j然后写一个函数判断s[i..j]是否回文。枚举区间是O(n^2)判断回文最坏是O(n)所以总复杂度是O(n^3)。当字符串长度到1000左右时这个复杂度在一秒量级下基本跑不完。看到O(n^3)的时候常规的优化思路会是能不能把判断回文的O(n)省掉于是你自然想到可以先判断短的区间然后把结果存下来等判断长区间时直接用。这其实就是动态规划的雏形——保存小区间的回文状态避免重复扫描。我用一个例子说明这种重复计算sabcba判断整个字符串是否回文最内层要比较a和a、b和b、c和c。而判断bcb的时候又比较了b和b、c和c。同一个c被反复比较了三次。一旦把“bcb是回文”这个结果缓存下来外层判断abcba时只查一次表就够了。2.2 找最长回文子序列枚举子集是指数爆炸子序列就不一样了。一个长度为n的字符串子序列总数是2^n个因为每个字符都有选或不选两种可能。n20就已经有上百万个组合n30更是超过十亿。这完全没法直接枚举。就算你用回溯加剪枝也逃不过指数级别的搜索空间。这时候动态规划的优势就极其明显它把指数问题通过重叠子结构压缩成了O(n^2)的区间递推。本质上是把“选了哪些字符”这个巨大的状态空间压缩成“区间左端点和右端点”两个维度。所以以后看到回文相关题目如果题目给出的是10^3甚至10^4级别的字符串长度基本可以直接锁定动态规划、中心扩展这类O(n^2)解法。指数级的搜索连边都摸不到。3. 647 回文子串布尔dp的细节都在遍历顺序里647题的dp设计非常经典几乎所有讲解回文区间的文章都会拿它当入门题。但我在刷题营里发现真正让很多人卡住的不是状态定义而是两层循环的遍历顺序。这题我前后写错过两次必须单独拉出来说说。3.1 dp[i][j]的含义与转移逻辑定义dp[i][j]为布尔值表示字符串s从下标i到下标j这段连续子串是否为回文。初始时所有dp[i][j]都是false只有满足条件才置为true。转移时分三种情况讨论i j即单个字符一定是回文dp[i][j] true。j i 1即两个字符相邻只要s[i] s[j]那么这两个字符组成的子串就是回文。j i 1此时整个子串是否回文取决于两端字符是否相等以及中间部分s[i1..j-1]是否回文即dp[i][j] (s[i] s[j]) dp[i1][j-1]。在写代码时可以把前两种情况合并如果s[i] s[j]并且j - i 1直接置true如果j - i 1就查dp[i1][j-1]。统计答案很简单每次dp[i][j]为true计数器加1即可。最终return计数。下面给一个Python核心代码段方便对照def countSubstrings(s: str) - int: n len(s) if n 0: return 0 dp [[False] * n for _ in range(n)] ans 0 for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] s[j]: if j - i 1: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j]: ans 1 return ans这段代码的循环写法不是随手写的遍历顺序是这题的重中之重下面详细解释。3.2 为什么i必须从大到小j从小到大看转移方程dp[i][j]依赖的是dp[i1][j-1]也就是说要计算某个位置的答案必须保证它的“左下角”已经被计算过。如果把i从0往n-1遍历j从i往n-1遍历会发生什么以i0为例计算dp[0][2]时需要dp[1][1]但此时i1那一行还没开始遍历dp[1][1]是初始值false结果就会错判。反过来让i从n-1往0遍历也就是从下往上计算每一行同时j从i往n-1遍历从左往右填充当前行就能保证用到dp[i1][j-1]时它已经算好了。因为左下角所在的i1行在下一行已经被外层循环先跑过。我经常用这个类比帮助记忆dp计算顺序要像填表格时“从下往上从左往右”地扫而不是按阅读习惯从上往下。很多人写错的根源就是把“阅读顺序”带到了“计算顺序”里。3.3 单独说说中心扩展法作为对照更理解dp647题其实还有一个不需要二维数组的解法中心扩展。枚举每个回文中心然后向两边扩展统计能扩出多少个回文子串。中心有两种一个字符奇数长度回文和两个字符偶数长度回文所以中心总数是2n-1个。中心扩展的时间复杂度同样是O(n^2)但空间是O(1)。我做过性能对比在n1000时二者差距不大n5000时中心扩展明显更快因为数组访问次数更少。那dp还有存在意义吗当然有。dp的思维方式更通用一旦题目变成“不仅要个数还要构造结果”或者“给出多个查询”dp的预处理优势就会体现出来。学习时不要只背一种解法两题放在一起时我建议先写dp再把中心扩展当优化技巧掌握。这样既理解本质又知道怎么应急。4. 516 最长回文子序列把转移方程一步步推到你自己都信516题的状态定义和647很像一开始很容易照搬过来设dp[i][j]为“从i到j这段子串的最长回文子序列长度”。这个方向是对的但转移方程推起来要更绕一点我甚至觉得这题的核心难点已经从“写代码”转移到了“说服自己为什么这个转移一定正确”。4.1 状态定义与相等情况dp[i][j]表示s[i]到s[j]这段区间内能挑出的最长回文子序列长度。初始化时dp[i][i] 1因为单个字符本身就是长度为1的回文子序列。当s[i] s[j]时这两个字符可以同时被纳入回文子序列的两端那么dp[i][j] dp[i1][j-1] 2。这个逻辑要仔细想想既然两端字符相同把它们同时选上一定不会亏因为中间部分s[i1..j-1]的最优回文子序列长度就是dp[i1][j-1]再加上这两个相同的字符长度必然最长。这里有个反直觉的细节即使dp[i1][j-1]是0加上2之后也可能比单纯只取一端更大。比如saai0, j1dp[1][0]不存在但可以视为0结果dp[0][1] 2完全正确。4.2 不相等情况只能二选一当s[i] ! s[j]时情况就复杂了。此时i和j不可能同时作为最长回文子序列的两端因为两端字符不同把它俩都选进去必然无法构成回文。所以最优解要么出现在丢掉s[i]后的区间[i1..j]里要么出现在丢掉s[j]后的区间[i..j-1]里。转移方程写作dp[i][j] max(dp[i1][j], dp[i][j-1])。理解这个方程的关键在于你要处理的不是一个必须使用所有字符的约束问题而是一个“可选可不选”的子序列问题。丢掉一端不会影响内部子序列的完整性只是让可选范围缩小了。所以取两个子问题的较大值就是当前区间的最优值。以scbbd为例期望输出是2bb。手动推一下dp[0][0] 1, dp[1][1] 1, dp[2][2] 1, dp[3][3] 1dp[1][2]中s[1]b, s[2]b相等所以dp[1][2] dp[2][1] 2 2dp[0][3]中s[0]c, s[3]d不等所以dp[0][3] max(dp[1][3], dp[0][2])。dp[1][3]中s[1]b, s[3]d不等继续取maxdp[0][2]中s[0]c, s[2]b不等继续取max。最终会推回dp[1][2]2得出答案2。整个递推过程就体现了区间DP的特点大区间的答案完全由更小区间的答案组合出来只不过这种组合不一定像回文子串那样只依赖一个方向。4.3 初始化和遍历方向的完整代码说明516的初始化除了dp[i][i]1之外还要注意dp[i][j]在j i时无意义。实现时可以让j从i1开始遍历避免覆盖初始化值同时也不会访问到无效状态。遍历顺序依然是从下往上、从左往右。因为dp[i][j]依赖dp[i1][j-1]、dp[i1][j]、dp[i][j-1]这三个位置分别在当前格的左下、正下、左方。只有让i从大到小、j从小到大才能保证这三个角度的值都已被计算。Python代码如下def longestPalindromeSubseq(s: str) - int: n len(s) dp [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] 1 for j in range(i 1, n): if s[i] s[j]: dp[i][j] dp[i 1][j - 1] 2 else: dp[i][j] max(dp[i 1][j], dp[i][j - 1]) return dp[0][n - 1]这里dp[i1][j-1]在j i1时访问的是dp[i1][i]也就是ji的无效位置但此时由于s[i]s[j]而且它们是相邻字符直接计算得到2。在Python中dp[i1][i]虽然存在但值为0所以结果是2刚好正确。不过依赖这个默认值总归有点隐晦我在代码里显式判断一下更稳妥if s[i] s[j]: if j i 1: dp[i][j] 2 else: dp[i][j] dp[i 1][j - 1] 2这个边界看起来很没存在感但第一次写的时候我就是因为没处理它在字符串长度为2且字符相同时得到1差点以为整个方程错了。排查了很久才发现是边界行为特此提醒。5. 两题放在一起对照才真正理解子串和子序列的思维差异刷题最忌“今天做647明天做516然后分别记住两种模板”。这两道题放在同一天本身就是希望你能在对比中提炼出更通用的方法论。我在复盘时做了一张对照表每次做相关题目前都会看一眼。对比维度647 回文子串516 最长回文子序列子结构要求连续不连续dp[i][j]含义区间[i, j]是否为回文子串区间[i, j]内最长回文子序列长度数据类型布尔值整数s[i] s[j]时取决于中间区间是否回文直接加2不用管中间是否回文s[i] ! s[j]时一定不是回文置false取max(dp[i1][j], dp[i][j-1])初始化默认全falsedp[i][i] 1答案统计遍历时计数true的个数返回dp[0][n-1]这张表里有几个值得细看的地方第一647中的“中间必须是回文”是硬约束因为子串本身连续只要里面有一段不是回文整体就不可能回文。但516不需要检查中间因为子序列可以跳过中间的字符只要两端相等内部怎么乱都能通过跳选来凑出回文。这就是为什么同样s[i]s[j]一个要看dp[i1][j-1]是否为true另一个可以直接2。第二647的答案不是dp[0][n-1]而是所有区间中true的数量之和。因为要求的是个数不是最长长度。不少初学者上手写完之后直接return dp[0][n-1]结果和答案差一大截原因就是没分清“存在性”和“最优值”。516则天然是“最优值”问题答案自然落在最后一个格子上。第三647的dp数组可以理解为一张“回文关系图”每个true单元都是一个合法回文子串516的dp数组则是“长度累积表”每个格子保存的是该区间内的最优解。前者重判断后者重计算。从这两题还能延伸出一个通用结论连续子串类的回文DP几乎都是“判断型布尔DP”而子序列类的回文DP几乎都是“区间最优值DP”。以后遇到类似“多少个回文子串”的问题先想布尔dp遇到“最长回文子序列”或“最长回文字符串长度”的问题再考虑数值dp。5.1 空间优化的进阶思路两题都用二维数组空间都是O(n^2)。在实际面试中如果面试官追问空间优化可以从这里入手。647的转移只依赖dp[i1][j-1]也就是下一行的左一列。如果按i倒序遍历其实可以只保留一行但仍然要处理j-1方向因为dp[i][j]还包含对dp[i][j-1]的依赖吗并不依赖它只依赖dp[i1][j-1]。所以理论上可以用一维数组但问题在于当前行的j从左向右遍历时dp[j-1]存的是当前行的值还是下一行的值如果内层j从小到大dp[j-1]在这一轮已经被更新成当前行而dp[i1][j-1]需要的是下一行的旧值这就冲突了。所以647的空间压缩不太直接需要引入额外变量或改变内层方向。我的建议是二维先行空间优化放到理解透彻后再考虑。516则不同它同时依赖三个方向滚动数组会更容易处理。可以用两个一维数组分别保存当前行和下一行每次更新前把下一行复制过来。这样空间降到O(n)代码量增加不多。实际做下来对于n1000的数据二维数组和滚动数组时间差异很小所以优化的核心价值在于内存而不是速度。6. 刷题营第四十五天的踩坑记录希望能帮你少走弯路最后分享几个我实际做这两道题时踩过的坑。这些问题不是知识点本身但恰恰是它们决定了你能否在限定时间内AC。6.1 遍历顺序写反运行结果玄学出错我第一次做647时顺手写成了i从0到n-1j从i到n-1结果在小样例上居然偶尔正确到了长一点字符串就开始漏数。原因是短字符串里很多区间在遇到s[i]s[j]且j-i1时中间区间不一定被提前算到就会漏判。这种“部分样例能过、长样例就挂”的体验非常折磨人。当时我把所有字符逐个打印观察才发现是计算顺序问题。从那以后凡是写区间dp我会先问自己一个问题dp[i][j]依赖哪些位置这些位置在我的循环顺序里是否已经计算完成把这个问题在注释里写出来基本就不会再错。6.2 j的范围从i开始还是i1开始跟初始化有关很多人做647时j从i开始因为单个字符也要计数做516时反而写j从i开始把dp[i][i]1的初始化覆盖掉然后结果double count。我的建议是647里j从i开始没问题因为每个单字符都是答案的一部分516里j从i1开始因为dp[i][i]1要在初始化阶段统一设置不要在循环里重复处理。两种写法都能过但务必保持一致别混着用。6.3 用打印dp表的方式验证推理过程如果你发现自己推的转移方程在小样例上不对最快的排查方式不是空想而是把dp表打印出来手动走一遍。比如拿saba跑647期望输出3分别对应三个起始位置不同的单字符和aba。我打印dp表后能看到dp[0][2]为true而这个true正是建立在dp[1][1]为true的基础上。一旦循环顺序写错dp[1][1]是falsedp[0][2]也会变成false肉眼一眼就能发现。516也一样打印dp表后能直观看到长度如何从对角线上的1一层层扩散到右上角。这种可视化对理解区间DP帮助极大胜过看十遍理论讲解。刷到第四十五天动态规划已经不再是单纯套模板的阶段了。回文类问题的价值不在于题目本身而在于它强迫你去区分“状态含义”和“依赖关系”这两个最容易混淆的东西。647和516一天做完我最大的体会是dp[i][j]到底存什么、依赖什么、怎么遍历这三个问题想透了代码基本就是翻译一遍而已。希望这篇记录也能让你少花一点在调试循环顺序上的时间。