各位打卡代码随想录的伙计们第四十五天来了。今天这两道题——647 回文子串、516 最长回文子序列——看起来名字只差两个字实际上一个是把字符串切成一段段判断是不是回文另一个是允许跳跃地凑出最长回文有多长。我在这天的任务单上做完之后就一个感受这两题放在同一天就是为了让你一次性把区间动态规划的两种典型玩法都吃透。如果你正卡在动态规划的入门门槛上尤其是对二维 DP 的遍历顺序、边界条件感到头大那这篇笔记应该能帮你省不少力气。我会从状态定义开始讲为什么这么定义再讲转移方程怎么来的最后把代码怎么写、踩过哪些坑、以及压缩空间的技巧全部摊开。文章比较长但跟着走完一遍这两道题你就基本拿稳了后续做最长回文子串、回文串插入次数之类的变形题也会顺很多。1. 整体设计与解题思路拆解1.1 两题共用一套区间 DP 框架先说一个整体判断647 和 516 都属于区间 DP的范畴处理的都是 s[i..j] 这个区间上的性质。区间 DP 的核心套路其实很固定第一步想清楚状态代表什么第二步找出区间的递推关系第三步确定填表的顺序。三件事缺一不可而这三件事在两题里分别指向了两个不同的方向。647 问的是有多少个回文子串回文这个性质天然适合从中间向外扩展一个区间是回文当且仅当它去掉首尾之后还是回文同时首尾字符相等。所以状态可以用布尔值表达这个区间是不是回文。而 516 问的是最长的回文子序列长度子序列可以跳着取字符所以要考虑的是在这个区间内能凑出的最长回文序列状态必须用整数记录最优长度。同样是区间 DP一个判真伪一个求极值。把这两题放在一起对比你对状态定义这件事的理解会比单刷任何一道都深刻得多。1.2 子串与子序列一字之差天壤之别这个区别我得单独拿出来说因为很多人栽就栽在这两个字上。子串必须是原字符串中连续的一段比如 abcde 里的 bcd 是子串但 bce 不是因为它跳过了字符 d。子序列不要求连续只要保持原有字符的相对顺序即可abcde 里的 ace 是合法的子序列因为你从左往右依次取出 a、c、e 三个字符。这个差异直接影响状态转移。回文子串要判断的是连续一段是否是回文两端如果相等就直接看去掉两端后的内部区间回文子序列要处理的是跳跃取字符当两端字符不相等时你不能确定是丢掉左边那个还是丢掉右边那个只能比较两种丢法哪种更好。这两道题我建议你分别拿 abcba 和 bbbab 两个样例手动跑一遍前者连续回文多后者靠跳着取字符才能拼出 bbbb。手动跑完你对子串连续、子序列可跳的理解会直接刻进脑子里。1.3 暴力解法到底差在哪在接触 DP 之前先看看不优化的解法长什么样这样才能真正理解 DP 解决了什么问题。647 的暴力做法是枚举所有子串区间。长度为 n 的字符串共有 n*(n1)/2 个子串每判断一个子串是不是回文最坏要逐个字符比较单次判断 O(n)总复杂度 O(n^3)。当 n 1000 时这大约是 5 亿次字符比较在普通机器上已经跑到秒级之外了题目稍微给个长字符串就直接超时。516 的暴力则更离谱因为子序列数量是指数级的枚举所有子序列再判断回文n 稍微大一点连跑都不敢跑。DP 的价值在于把重复判断变成查表记忆。647 只需要 O(n^2) 的时间和空间每个区间是否回文都能在常数时间内从更小区间的结果推出来。516 同样用 O(n^2) 的表格记录每个区间的最优长度最终答案就藏在 dp[0][n-1] 里。从指数级或三次方级降到平方级这就是动态规划对这类问题的降维打击。2. 647 回文子串从内向外扩散的区间判断2.1 状态定义为什么用布尔数组647 的题目要求很明确返回字符串 s 中回文子串的个数。我这里采用的经典状态定义是dp[i][j] 表示字符串 s 从下标 i 到下标 j 这一整段包含两端是不是回文子串是则 true否则 false。为什么是布尔类型而不是整数因为我们要的不是这段有多长而是这段能不能构成一个回文。回文是个二值属性不存在半回文的状态。当你把所有区间的真伪都确定后统计其中 true 的个数就是答案。这种定义最大的好处是方便转移。判断一个大区间是否回文完全不需要重新比较一大堆字符只需要知道两个信息两端字符是否相等以及去掉两端后的内部区间是否回文。这两个信息要么 O(1) 直接比较要么已经在 dp 表里查得到整道题的计算量就从 O(n^3) 直线下降到 O(n^2)。2.2 转移方程的分支细节写转移方程时通常分成两段来看当 s[i] ! s[j] 时两端都不同这个区间肯定不是回文dp[i][j] 保持 false。当 s[i] s[j] 时还要看区间长度如果 j - i 1也就是区间长度为 1 或 2直接判定为 true。单字符本身是回文两个字符只要相等那当然也是回文。如果 j - i 1那么需要看内部区间 dp[i1][j-1] 是否为 true。如果内部是回文加上相等的外壳整体就是回文否则整体不是。顺便解释一下为什么 j - i 1 要单独处理。当区间长度为 2 时dp[i1][j-1] 会访问到类似 dp[i1][i] 这样的位置左边下标大于右边下标表示一个不存在的空区间。这个空区间的值到底是 true 还是 false在不同语言里不好统一处理索性直接特判短区间逻辑上更干净也不会出错。举个例子s aba。初始化时 dp[0][0]、dp[1][1]、dp[2][2] 都为 true。然后处理长度为 2 的区间dp[0][1] 中 s[0] as[1] b不相等falsedp[1][2] 中 s[1] bs[2] a不相等false。最后处理长度为 3 的区间 dp[0][2]首尾 a 和 a 相等且 j - i 2 1查内部 dp[1][1] 是 true所以 dp[0][2] true。整个表里 true 的格子有 3 个答案就是 3。这个例子虽然简单但足以验证状态定义和转移方程是否自洽。2.3 遍历顺序必须先填内部小区间这是 647 最容易翻车的地方我必须单独强调。从转移方程可以看到dp[i][j] 依赖 dp[i1][j-1]也就是说当前区间依赖的是一个左下角方向的更小区间。如果你用普通的双重循环i 从 0 到 n-1、j 从 i 到 n-1 去填表会发现计算 dp[i][j] 时dp[i1][j-1] 可能还没有被计算出来读到的就是初始默认值 false最终答案会严重偏小。正确做法有两个等价的选择一是按区间长度从小到大填表先填所有长度为 1 的区间再填长度为 2 的依此类推二是让外层 i 从 n-1 倒着走到 0内层 j 从 i 走到 n-1。我习惯用第二种写成代码非常直白def countSubstrings(s: str) - int: n len(s) dp [[False] * n for _ in range(n)] result 0 for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] s[j] and (j - i 1 or dp[i 1][j - 1]): dp[i][j] True result 1 return result为什么 i 倒序就一定安全因为每轮外层循环都在处理更小的左边界而 dp[i1][j-1] 里的 i1 大于当前的 i在之前的外层循环里已经填过了。同时内层 j 从小到大j-1 也已经在当前行的左侧位置填过。这样每次查询依赖项时数据都是现成的。你可以把 dp 表画成一个矩阵观察依赖方向这个结论一目了然。顺带一提答案统计我直接在判断成立时 result 1省得最后再遍历一次 dp 表数 true。这种边填边统计的小习惯在代码里看起来只是省了一行实际上能让思路更清晰我们要求的本来就是 true 的个数没必要留到后面二次扫描。2.4 中心扩展法面试官会追问的另一种解法如果你只用 DP 解出 647面试官很可能会追问一句还有没有其他思路这时候中心扩展法就是必须要掌握的备选方案。中心扩展法的思路是每个回文子串都有一个中心点。长度为奇数的回文中心是一个字符长度为偶数的回文中心是两个字符之间的空隙。以这个中心为起点同时向左右两边扩展只要两边的字符相等就说明找到了一个新的回文子串可以继续往外扩直到边界或字符不等为止。字符串长度为 n 时中心点一共有 2n - 1 个n 个单字符中心加 n - 1 个空隙中心。每个中心最多扩展 O(n) 次总时间复杂度是 O(n^2)空间复杂度 O(1)。核心代码也很短def countSubstrings(s: str) - int: n len(s) result 0 for center in range(2 * n - 1): left center // 2 right left center % 2 while left 0 and right n and s[left] s[right]: result 1 left - 1 right 1 return result这里的 center 把奇数中心和偶数中心统一处理了center 是偶数时left right对应单字符中心center 是奇数时left 1 right对应空隙中心。这个思路在工作中也经常用到比如检测 DNA 序列中的回文结构、日志分析里的对称模式匹配都可以用它快速过一遍。我自己做题时通常先用中心扩展 AC 一版因为写起来快、空间占用小再回头用 DP 写一版因为 DP 的思维对后续 516 帮助很大。两种方法各有各的用武之地建议你两版都写一遍。3. 516 最长回文子序列从两侧夹逼的最长长度3.1 状态从是不是升级为有多长516 的题面是给定字符串 s返回最长回文子序列的长度。子序列允许跳跃取字符所以这题不能用 647 那套布尔状态直接套。我用的是经典区间 DP 定义dp[i][j] 表示字符串 s 在区间 [i, j] 内能取到的最长回文子序列长度。dp[i][i] 显然是 1因为单个字符本身就是一个长度为 1 的回文子序列。区间长度为 0 时可以视为 0。这个定义和 647 最大的不同在于dp 数组里存储的不再是是或否而是最佳长度值这才符合题目求极值的要求。为什么要针对区间而不是前缀来定义状态因为回文子序列可能取到区间中间位置的字符也可能同时取到两端字符如果用一维的前缀 DP 就很难表达两端同时保留这种情况。区间 DP 天然适合这种需要同时照顾左右两侧的状态设计。3.2 两端相等与两端不等的两种决策接下来是转移方程分两条路当 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])。第一条路为什么可以直接 2因为内部区间 [i1, j-1] 的最长回文子序列长度是 dp[i1][j-1]我在这个序列的两端分别加上 s[i] 和 s[j]由于这两个字符相等整体仍然是回文长度自然增加了 2。而且这一定是最优的因为任何以该区间为基础的回文子序列如果能用上这两个相等端点确实比不用时更长。这个直觉在动态规划里属于比较可靠的一类。第二条路比较像取舍问题。两端不相等时ss[i] 和 s[j] 不可能同时出现在同一个回文子序列的两端那我们只能二选一要么忽略 s[i]问题退化为区间 [i1, j] 的最优解要么忽略 s[j]问题退化为区间 [i, j-1] 的最优解。取两者较大值就是当前区间的最优解。这个思路和编辑距离里删除某个字符看哪种操作代价更小非常类似。拿 bbbab 验证一下。n 5全部区间计算完后dp[0][4] 应该是 4对应 bbbb。拿 cbbd 验证dp[0][3] 是 2对应 bb。这两个经典用例你可以在写完代码后直接跑跑通了基本说明方程没问题。3.3 初始化与遍历顺序的细节处理516 的初始化逻辑比 647 多一个关键点dp[i][i] 1。有人可能会问长度为 1 的字符难道不能靠转移方程推出来吗问题是转移方程需要先有内部区间或相邻区间而长度为 1 的区间没有任何可参考的邻居所以必须手工指定初值。把 dp[i][i] 全部赋为 1 之后长度为 2 的区间就可以正常计算了。遍历顺序依然是核心。从转移方程看dp[i][j] 依赖 dp[i1][j-1]、dp[i1][j]、dp[i][j-1] 三个值。为了保证这三个值都已经算好继续采用 i 从 n-1 到 0、j 从 i1 到 n-1 的遍历顺序。注意 j 从 i1 开始因为 dp[i][i] 已经初始化过了不需要再覆盖。代码长这样def longestPalindromeSubseq(s: str) - int: n len(s) dp [[0] * n for _ in range(n)] for i in range(n): dp[i][i] 1 for i in range(n - 1, -1, -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]关于空区间问题这里也有个小细节。当 j i 1 且 s[i] s[j] 时会计算 dp[i1][i] 2也就是访问到了左边下标大于右边下标的无效区间。由于二维数组默认值是 0dp[i1][i] 的 0 恰好表示空区间的最长回文子序列长度为 0最终结果就是 2逻辑完全正确。所以在这里默认初始化为 0不只是一个习惯更是对空区间的隐式表达。如果你把它初始化成别的值边界判断就要重写。3.4 一维滚动数组写法与 pre 变量的含义516 的空间可以优化到 O(n)因为每一行 dp[i][..] 只依赖上一行 dp[i1][..] 和当前行的左侧值 dp[i][..][j-1]。滚动数组代码如下def longestPalindromeSubseq(s: str) - int: n len(s) dp [0] * n for i in range(n - 1, -1, -1): dp[i] 1 pre 0 for j in range(i 1, n): temp dp[j] if s[i] s[j]: dp[j] pre 2 else: dp[j] max(dp[j], dp[j - 1]) pre temp return dp[n - 1]这个 pre 变量是滚动数组里最容易被忽略的关键点。解释一下内层循环开始前dp[j] 里保存的还是上一行的第 j 列也就是 dp[i1][j]。进入循环后我们先把 dp[j] 的旧值存到 temp再更新 dp[j]。而下次迭代时这个 temp 就变成了 上一行的第 j-1 列正好对应转移方程里的 dp[i1][j-1] 斜对角依赖于是传给 pre 使用。如果你直接把二维版的代码简写成没有 pre 的一维版大概率会在处理 s[i] s[j] 的斜对角依赖时取到已经被覆盖的值结果时对时错。我建议平时练习时就理解这个变量的作用不要只背代码。面试时若要求空间优化你能把为什么用 pre 讲清楚比单纯甩出一段正确代码更能加分。4. 常见问题与排查技巧实录4.1 答案偏小的两个常见原因我在带朋友刷这题时发现 647 答案偏小几乎都出在同一个地方遍历顺序反了。因为 dp[i][j] 依赖 dp[i1][j-1]如果 i 是从 0 到 n-1 正着走很多内部小区间还没算出来扫到的都是初始 false统计时自然少了一大批 true。排查方法很简单你把 dp 表打印出来看看类似 dp[0][最后] 这种长区间是不是错误地变成 false如果是先检查遍历顺序不要急着改转移方程。还有一类原因是统计遗漏。有些人写完循环后只在某个 if 里面累加 result却没有覆盖所有动态转移分支。比如只在 s[i] s[j] 时加却忘了单字符区间从一开始就应该算进答案。要避免这个问题最简单的方法是在状态转移成功后统一累加而不是在各个分支里重复加。4.2 516 比原字符串长度多算一位516 的常见错误是dp[0][n-1] 返回的长度比正确答案大 2。这通常是因为初始化时把 dp[i][i] 都设成了 2或者把 dp 默认值填成了 1。回文子序列的最短长度是 1单字符区间不能凭空多算长度。检查时先从 a 这种单字符输入开始测期望值是 1再从 aa 测期望值是 2。两步都能过边界基本就没问题。另外当 s[i] s[j] 且 j i 1 时如果你没有保证 dp[i1][i] 的位置是 0而是被初始化成了 1那么 dp[i][j] 会变成 3比正确答案多 1。这里的排查思路是出现比预期多 1 或 2的情况九成是空区间的默认值错了优先检查初始化部分而不是转移方程。4.3 滚动数组时对不上二维版结果如果你写了 516 的二维版和滚动数组版却发现两者结果不一致请重点检查 pre 和 temp 的赋值时机。我第一次写滚动数组时就栽过先把 dp[j] 更新完再用 pre 存旧值结果 pre 拿到的是新值斜对角依赖就全错了。调试技巧是拿一个较长的回文串比如 aabbaa分别打印二维版每一行和滚动数组版每一轮更新后的数组逐列对比。如果某一行从某列开始出现差异那问题基本就锁定在那个列之前的 pre 处理逻辑上。这种对比调试方法对所有滚动数组问题都适用不只是 516。4.4 边界条件速查表最后把这天两道题的边界条件整理成一张表方便你复习时快速回忆。问题状态含义初始化依赖方向答案取值647 回文子串dp[i][j] 是否回文dp[i][i] true默认 false依赖 dp[i1][j-1]统计 true 的总数516 最长回文子序列dp[i][j] 区间内最长回文子序列长度dp[i][i] 1默认 0依赖 dp[i1][j-1]、dp[i1][j]、dp[i][j-1]dp[0][n-1]表格里没有直接写出来但实际编码时必须记住的还有两点647 的 j 从 i 开始516 的 j 从 i 1 开始两者外层遍历 i 都从 n-1 到 0。这两条规则配合表格一起记基本不会出错。5. 个人刷题心得与后续扩展5.1 先画表再写代码说句实在话我做区间 DP 到现在最管用的技巧反而不是背公式而是先画表再写代码。拿到一道题先在纸上画一个 n 乘 n 的表格标出 dp[i][j] 有哪些依赖项然后用手箭头把依赖方向画出来。看到依赖项在右上方就意识到必须让 i 倒序遍历看到依赖项在左下方就要思考如何提前计算。这个步骤花不了两分钟但能避免绝大多数遍历顺序错误。画表的另一个好处是能直观看出空间优化的可能性。比如 516 的依赖项集中在相邻两行之间你会发现滚动数组压一维完全可行但有些 DP 问题依赖范围横跨好几行强行压缩反而会引入大量临时变量得不偿失。这种判断力恰恰是通过画表练出来的。5.2 两题可以自然衔接到哪些变形题把 647 和 516 吃透之后后续有几道题你基本可以无缝衔接。第一道是 LeetCode 5最长回文子串。直接复用 647 的 dp 表扫一遍所有区间找出最长的 true 区间即可也可以用中心扩展法记录扩展过程中最长的区间边界。第二道是 LeetCode 1312让字符串成为回文串的最少插入次数。答案就是 n - dp[0][n-1]因为在一个序列里原本是回文子序列的部分不需要动其余每个不在回文子序列中的字符都要找一个对应字符插到另一边最少插入次数就是总长度减去已存在的最长回文子序列长度。这两道题做完你对回文 DP这一整个小专题的掌握度会扎实很多。回到第四十五天本身。代码随想录把这两题排在一起表面上看都是字符串回文实际上是在训练你同一个区间 DP 框架下处理判断型问题和最值型问题的能力。状态定义不同、转移方程不同、统计方式不同但填表顺序的底层逻辑完全一致。如果你能把两题的推导过程完整地讲给同伴听而不是只背结论那这一天的内容才真正属于你了后面再做同类题目会明显轻松不少。