647回文子串与516最长回文子序列：区间DP两种典型玩法全解析

各位打卡代码随想录的伙计们，第四十五天来了。今天这两道题——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*(n+1)/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 转移方程的分支细节

写转移方程时，通常分成两段来看：

1. 当 s[i] != s[j] 时，两端都不同，这个区间肯定不是回文，dp[i][j] 保持 false。
2. 当 s[i] == s[j] 时，还要看区间长度：
   • 如果 j - i <= 1，也就是区间长度为 1 或 2，直接判定为 true。单字符本身是回文，两个字符只要相等，那当然也是回文。
   • 如果 j - i > 1，那么需要看内部区间 dp[i+1][j-1] 是否为 true。如果内部是回文，加上相等的外壳，整体就是回文；否则整体不是。

顺便解释一下为什么 j - i <= 1 要单独处理。当区间长度为 2 时，dp[i+1][j-1] 会访问到类似 dp[i+1][i] 这样的位置，左边下标大于右边下标，表示一个不存在的空区间。这个空区间的值到底是 true 还是 false，在不同语言里不好统一处理，索性直接特判短区间，逻辑上更干净，也不会出错。

举个例子，s = "aba"。初始化时 dp[0][0]、dp[1][1]、dp[2][2] 都为 true。然后处理长度为 2 的区间：dp[0][1] 中 s[0] = 'a'，s[1] = 'b'，不相等，false；dp[1][2] 中 s[1] = 'b'，s[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[i+1][j-1]，也就是说当前区间依赖的是一个"左下角"方向的更小区间。如果你用普通的双重循环，i 从 0 到 n-1、j 从 i 到 n-1 去填表，会发现计算 dp[i][j] 时，dp[i+1][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[i+1][j-1] 里的 i+1 大于当前的 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[i+1][j-1] + 2。
• 当 s[i] != s[j] 时，两端不能同时使用，只能选择丢掉其中一个端点，然后看剩下哪种丢法更优，即 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

第一条路为什么可以直接 +2？因为内部区间 [i+1, j-1] 的最长回文子序列长度是 dp[i+1][j-1]，我在这个序列的两端分别加上 s[i] 和 s[j]，由于这两个字符相等，整体仍然是回文，长度自然增加了 2。而且这一定是最优的，因为任何以该区间为基础的回文子序列，如果能用上这两个相等端点，确实比不用时更长。这个直觉在动态规划里属于比较可靠的一类。

第二条路比较像"取舍"问题。两端不相等时，ss[i] 和 s[j] 不可能同时出现在同一个回文子序列的两端，那我们只能二选一：要么忽略 s[i]，问题退化为区间 [i+1, 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[i+1][j-1]、dp[i+1][j]、dp[i][j-1] 三个值。为了保证这三个值都已经算好，继续采用 i 从 n-1 到 0、j 从 i+1 到 n-1 的遍历顺序。注意 j 从 i+1 开始，因为 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[i+1][i] + 2，也就是访问到了左边下标大于右边下标的无效区间。由于二维数组默认值是 0，dp[i+1][i] 的 0 恰好表示空区间的最长回文子序列长度为 0，最终结果就是 2，逻辑完全正确。所以在这里"默认初始化为 0"不只是一个习惯，更是对空区间的隐式表达。如果你把它初始化成别的值，边界判断就要重写。

3.4 一维滚动数组写法与 pre 变量的含义

516 的空间可以优化到 O(n)，因为每一行 dp[i][..] 只依赖上一行 dp[i+1][..] 和当前行的左侧值 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[i+1][j]。进入循环后，我们先把 dp[j] 的旧值存到 temp，再更新 dp[j]。而下次迭代时，这个 temp 就变成了 "上一行的第 j-1 列"，正好对应转移方程里的 dp[i+1][j-1] 斜对角依赖，于是传给 pre 使用。

如果你直接把二维版的代码简写成没有 pre 的一维版，大概率会在处理 s[i] == s[j] 的斜对角依赖时取到已经被覆盖的值，结果时对时错。我建议平时练习时就理解这个变量的作用，不要只背代码。面试时若要求空间优化，你能把为什么用 pre 讲清楚，比单纯甩出一段正确代码更能加分。

4. 常见问题与排查技巧实录

4.1 答案偏小的两个常见原因

我在带朋友刷这题时，发现 647 答案偏小几乎都出在同一个地方：遍历顺序反了。因为 dp[i][j] 依赖 dp[i+1][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[i+1][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 的 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 框架下处理"判断型问题"和"最值型问题"的能力。状态定义不同、转移方程不同、统计方式不同，但填表顺序的底层逻辑完全一致。如果你能把两题的推导过程完整地讲给同伴听，而不是只背结论，那这一天的内容才真正属于你了，后面再做同类题目会明显轻松不少。