开始刷到第四十五天字符串相关的动态规划算是快收尾了。今天这两道题647回文子串和516最长回文子序列放在一起刷其实挺有意思——同样都是“回文”一个要求连续的子串一个允许不连续的子序列解法上的差异和共通点正好能帮人把二维DP的遍历顺序彻底想明白。如果你正在跟代码随想录算法营或者刚刷完编辑距离那一批题这两道可以作为字符串DP的收尾练习如果你是零基础刚起步也不用怕今天的内容我会从最基础的暴力思路讲起把每一步推导掰开来说。1. 把题目拆清楚子串、子序列、回文三个词别混1.1 回文子串与回文子序列的本质差别先看两个词。“回文子串”要求字符在原字符串里是连续的比如abcba里的bcb是回文子串ab cba中间不管怎么切取出来的字符在原串里必须是紧紧挨着的。而“回文子序列”不要求连续只要求保持相对顺序比如bbbab里我们可以隔着字符取bbbb它不连续但确实是回文子序列。这个差别直接决定了算法的形态。连续意味着我们可以枚举每个位置向两边扩张不连续意味着我们要考虑“跳过某个字符”的可能性这就天然指向了区间DP——用dp[i][j]表示从i到j这一段区间的状态通过端点字符是否相等来决定往哪个子区间转移。很多初学者会把两道题混在一起看觉得都是“统计回文”或者“找最长回文”但写代码时就会发现子串题用的是二维布尔数组来标记(i,j)区间是否为回文子序列题用的是二维整数数组来记录区间内的最长回文长度。数据结构选型不同遍历顺序不同初始化策略也不同这些细节串起来才是这两道题的完整考点。1.2 暴力解法到底有多贵为什么要优化先给自己一个直观感受。对于647一个最简单的暴力是枚举所有子串的起点和终点再写一个isPalindrome函数去判断这样枚举起点终点是O(n²)每个子串判断又是O(n)总复杂度O(n³)。字符串长度到100这个方案还勉强能跑但力扣的测试数据一上来超时是必然的。至于516如果枚举所有子序列那就是2的n次方级别压根不是能写出来的算法。所以两道题的第一课都是暴力枚举作为起点用来验证思路没问题但最终解法必须做到O(n²)以内。647的O(n²)解法有两条路一条是中心扩展一条是动态规划516则基本只有动态规划这一条正路中心扩展在这里派不上用场因为子序列允许跳过字符单靠左右指针扩张覆盖不了“中间隔了几个字符再匹配”的情况。这里也回应一个很多人问过的问题为什么两道题都用二维DP因为回文天然是区间属性——s[i..j]是否是回文、s[i..j]的最长回文子序列长度都只和这个闭区间本身有关和区间外面的字符无关。把大区间拆成小区间小区间的答案可以递推出来这就是区间DP的基本盘。2. 647 回文子串中心扩展法和动态规划两条路线都值得写一遍2.1 中心扩展法O(1)空间的漂亮解法先讲中心扩展因为我个人觉得这道题用中心扩展更直观代码也短。思路一句话遍历所有可能的回文中心然后向两边扩张只要左右字符相等就算发现一个回文子串。这里最关键的是中心的数量。一个长度为n的字符串回文中心不只有n个而是2n - 1个。为什么因为回文分两种奇数长度的回文有一个中心字符比如aba的中心是b偶数长度的回文中心在两个字符之间比如abba的中心在b和b中间不是一个具体的字符。所以中心扩展要拆成两种情况分别处理class Solution { public: int countSubstrings(string s) { int n s.size(); int ans 0; for (int i 0; i n; i) { // 奇数长度回文中心是i ans expand(s, i, i); // 偶数长度回文中心在i和i1之间 ans expand(s, i, i 1); } return ans; } int expand(const string s, int left, int right) { int count 0; while (left 0 right s.size() s[left] s[right]) { count; left--; right; } return count; } };我最早学这个写法的时候有个困惑expand(s, i, i)是不是只记了一个回文比如aaa以第二个a为中心扩展会依次发现a、aaa所以一次expand返回的其实是“以这个中心能扩张到的所有回文子串数量”不只是1个。理解这一点就不会在计数时出错了。这个解法的时间复杂度是O(n²)空间复杂度是O(1)不用开二维数组实测在LeetCode 647上表现相当好。很多教科书喜欢拿DP做这道题但面试时如果能先给中心扩展通常会让面试官眼前一亮因为空间上明显优于二维DP。2.2 动态规划法为区间DP打下的地基既然今天的另一道题要用DP647也用DP写一遍正好把二维布尔DP的套路练熟。定义dp[i][j]表示s[i..j]闭区间是否为回文子串是布尔值。递推的核心逻辑是如果s[i] s[j]并且区间长度小于等于3或者dp[i1][j-1]是回文那么dp[i][j]就是回文。为什么长度小于等于3要单独判断因为当j - i 2时比如a、aa、aba去掉首尾后剩下的区间要么是空的要么只有一个字符它们天然是回文不需要依赖dp[i1][j-1]。如果直接去查dp[i1][j-1]在i1 j-1的情况下下标就乱套了。这里有个细节我必须提醒你遍历顺序必须从下往上、从左往右。因为dp[i][j]依赖dp[i1][j-1]也就是左下角的值。如果你按i从0到n-1、j从i到n-1的顺序遍历那么计算dp[0][3]时dp[1][2]还没来得及算查出来就是个错误值。正确做法是让i从大到小j从小到大class Solution { public: int countSubstrings(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n, false)); int ans 0; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j]) { if (j - i 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } if (dp[i][j]) ans; } } return ans; } };很多同学第一次写会漏掉j i这个条件或者把j的起点写成0结果访问了大量j i的无意义位置。其实对角线以下的区域我们根本不用管j从i开始就可以了。两条路线的取舍我个人的建议是笔试或日常刷题用动态规划因为和后续的516能形成方法上的连贯面试手撕用中心扩展因为代码短、空间好、边界处理直观。两种都会写才是这道题的正确打开方式。3. 516 最长回文子序列二维DP里最难的那一类不在递推在初始化3.1 DP定义与递推公式的推倒过程如果说647的DP是二维布尔表的“入门款”516的DP就是二维整数表的“进阶款”。先定义dp[i][j]字符串s[i..j]范围内最长回文子序列的长度。这个定义和647有本质区别——647记录的是“是或不是”516记录的是“有多长”前者是状态判断后者是数值统计。递推公式分两种情况当s[i] s[j]时说明两端字符可以同时收进回文子序列那么dp[i][j] dp[i1][j-1] 2。这里加2是因为首尾两个字符都算上了。当s[i] ! s[j]时说明s[i]和s[j]不可能同时出现在同一个回文子序列的首尾那我们只能二选一要么放弃s[i]看dp[i1][j]要么放弃s[j]看dp[i][j-1]。取两者的最大值。写成代码class Solution { public: int longestPalindromeSubseq(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); for (int i 0; i n; i) dp[i][i] 1; for (int i n - 1; i 0; i--) { for (int j i 1; j n; j) { 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[i][i] 1这一步必须在双重循环之前做好因为单个字符本身就是长度为1的回文子序列。如果你只初始化dp为0那么计算dp[i][i1]这种长度为2的区间时如果s[i] ! s[j]结果会变成0但正确答案应该是1——你至少可以选其中任意一个字符作为长度为1的回文子序列。另一个细节是循环里j从i 1开始因为dp[i][i]已经初始化了不需要在转移里再处理。如果你写成j i在dp[i][i]上套公式当s[i] s[i]时会得到dp[i1][i-1] 2这个区间是非法区间结果就错了。3.2 区间长度的推进顺序决定你代码能不能一次跑对516的遍历顺序比647更容易写错。在647里dp[i][j]依赖dp[i1][j-1]同样是左下角所以需要i倒序、j正序。516除了依赖左下角还依赖左侧和下方即dp[i][j-1]和dp[i1][j]。如果i倒序、j正序这两个依赖也都能在计算dp[i][j]之前得到因为j-1在当前行左侧已经在这一行算过了i1在下一行上一轮外层循环算过了。可如果你把外层i写成正序内层j从i 1开始那么计算dp[i][j]时dp[i1][j-1]和dp[i1][j]都还是初值0递推就变成了纯靠初始化的假结果整张表全是错的。我当时在这道题栽过一次后来想了个笨办法帮助记忆看你的dp表怎么画依赖关系指向哪个方向遍历方向就跟依赖相反。dp[i][j]依赖左下角所以必须从表的右下方往左上方填具体就是一行的j从左往右但行要自下而上。这和二维数组的“行优先”直觉正好相反所以特别容易错。这道题还可以顺带证明一个性质dp[i][j]不会小于dp[i1][j]也不会小于dp[i][j-1]因为区间越大包含的字符越多最长回文子序列长度只可能增加。这个性质保证了当s[i] ! s[j]时取max是安全的不会出现“区间变长反而答案变小”的诡异情况。4. 两题对照数据结构的差异决定了遍历方向的不同4.1 同样是区间DP为什么一个用bool一个用int把647和516的代码放在一起看最直观的差异是dp表的类型。647的dp是vectorvectorbool因为每个区间只需要回答“是不是回文”516的dp是vectorvectorint因为每个区间要回答“最长回文子序列有多长”。类型的差异背后是信息量的差异。647里我们一旦知道dp[i][j]是回文就计数加1不需要继续叠加长度516里我们要把子问题的解“合并”起来合并的操作是加法或取max这要求dp的值本身就保存了数值信息。这也是为什么有些同学会试着用647的DP思路去解516结果发现计数逻辑完全用不上——因为两道题虽然在同一个“回文”主题下但目标函数不同一个是统计个数一个是求解最大值统计问题适合布尔标记最值问题适合数值叠加。4.2 面试时怎么快速决定用哪种解法如果面试官给的是“求回文子串个数”我的第一反应一定是中心扩展法。原因有三个代码量最小出错概率低空间O(1)能体现复杂度意识扩展过程直观方便向面试官解释思路。如果你先用DP写647面试官追问“能不能优化空间”你再改写中心扩展虽然也能圆回来但不如一开始就给出空间更优的方案来得清爽。如果面试官给的是“最长回文子序列长度”那就只能走DP没有中心扩展的捷径。这个时候我会先花三十秒说清楚三件事dp[i][j]的含义、s[i]s[j]和s[i]!s[j]两个分支、i倒序j正序的遍历原因。把这三件事讲明白代码本身反而是最不重要的。从学习顺序上我也建议先看647再看516。647的递推里没有max分支很单纯适合建立“区间DP”的直觉516在647的基础上加入了“放弃一端字符”的转移逻辑理解难度上一个台阶但一旦想通编辑距离类的题目你会顺手很多因为它们同样是在做“匹配成功就加一、匹配失败就在两个子问题里取最优”的事。5. 高频报错与易错点实录这些坑我替大家踩过了5.1 遍历顺序写反是最隐蔽的Bug这类区间DP的for循环顺序写错往往不报编译错误也不报数组越界就是结果不对。我见过太多人拿着for (int i 0; i n; i) for (int j i 1; j n; j)的代码来问为什么输出是1一看就知道是依赖的左下角还没算。这里给你一个“一眼定位”的方法在循环体内临时把dp[i][j]打出来对比手算的小例子bbbab如果第一行第一列是一些莫名其妙的0基本就是遍历方向错了。更快的定位方法是直接检查j i 1那一层斜线的填表顺序——用表格画出来你会发现正确的填法是从右下角出发一层一层往左上角推像剥洋葱一样。5.2 647 DP里的j - i 2到底覆盖了哪些情形很多刚开始写647 DP的同学会纠结这个边界条件到底该取 1还是 2。我们拆开看当j - i 0只有一个字符a回文当j - i 1两个字符aa只要相等就是回文当j - i 2三个字符aba只要首尾相等中间不管是什么都只有一个字符天然回文。所以j - i 2是准确的三种情况全覆盖。如果写成j - i 1长度为3的回文aba就会走dp[i1][j-1]也就是去查dp[1][1]这个值是true结果也能对。但写成 2更安全逻辑也更清晰长度不超过3的区间不需要依赖子区间。建议记住这个结论面试时能直接说出“长度小于等于3的区间一定回文”的原因会让面试官觉得你的边界意识很到位。5.3 516的返回值到底取哪里516的答案在dp[0][n-1]也就是整个字符串区间的最长回文子序列长度。这个位置在表格的右上角是最后填完的一个位置。很多同学会在循环结束后额外扫一遍dp求最大值其实没必要——dp[0][n-1]已经覆盖了全长区间而dp[i][j]随着区间扩大只增不减所以右上角天然是全局最大值。额外扫描不会错但说明你对“区间DP天然满足最优子结构”的理解还差了点火候。另外516有一个初始化的隐藏要求n 1时循环体一次都不进直接返回dp[0][0] 1。这个用例能帮你验证自己的初始化代码是否干净。如果你忘了给dp[i][i]赋值输入a就会返回0这属于最典型的低级错误。5.4 字符串处理题里常见的时间复杂度陷阱写647中心扩展的时候很多人会问“这里不是嵌套了两层循环为什么是O(n²)而不是O(n³)”因为内层while虽然可能扩展很长但在每个中心上扩展的总步数和字符串长度相关对2n - 1个中心来说最坏情况的扩展总长度是O(n)平摊到每次扩展还是O(n)。具体来说所有中心扩展步数之和的量级是O(n²)比如全aaaa这种情况下每个中心扩展步长接近n/2但乘上中心数仍是n²级别。想象一个长方形横轴是中心序号纵轴是扩展半径所有小矩形的总面积不会超过n²这就是O(n²)的直观来源。而516的DP是标准的双重循环每一对(i, j)都做常数次操作所以也是O(n²)时间但空间是O(n²)。如果面试官继续追问空间优化516理论上可以优化到O(n)因为每一行只依赖下一行和当前行的前一个位置可以用滚动数组但面试通常不会强制要求因为代码复杂度会上升不少。6. 实操心法这道题之后你对二维DP的理解会不一样6.1 用一个自测用例串起所有边界我自己刷完这两道题固定用一组用例来验证代码是否正确。647用aaa期望答案是6a出现3次aa出现2次aaa出现1次3216。516用bbbab期望答案是4因为最长回文子序列是bbbb再用cbbd期望答案是2因为bb或者c长度为1都可以取。如果这些用例一次通过代码基本就没问题。再补一个细节647的aaa其实是中心扩展法最好的测试用例因为奇数中心和偶数中心都很多能同时检验两种中心类型。如果代码输出不是6通常问题出在中心遍历范围上——比如只遍历了奇数中心漏掉了偶数中心输出会少一半。6.2 为什么说这两道题是字符串DP的分水岭在代码随想录算法营的进度里第45天意味着你已经见过不少DP题型了背包、打家劫舍、股票问题、编辑距离。回文这两题看似在“字符串”里打转实际上把区间DP的核心思想完整曝光了一遍区间定义、端点匹配与放弃、子区间依赖、遍历方向、初始化边界。学会了这套东西很多经典面试题都会迎刃而解。比如131. 分割回文串需要先预处理任意子串是否是回文本质上就是647的DP表又比如1143. 最长公共子序列它的dp递推和516长得几乎一样区别只是两个字符串和两个指针的移动策略。所以今天这两道题不是终点而是给后面这些“更长的串”打底。6.3 最后分享一个刷题节奏上的体会这一天两道题看起来不多但加上复盘和写笔记我一般会预留一个半小时。第一遍先不看题解尝试中心扩展解647如果DP能自己推出来就更好516建议哪怕写不出来也要先把自己的递推思路写到纸上卡住了再看题解——这比直接抄答案记住得更牢。今天这两道题最值得收藏的一句话是回文子串用中心扩展回文子序列用区间DP。当你看到题目里带着“子序列”三个字基本上就和连续算法说再见了接下来要做的第一件事一定是思考能不能用区间DP建模。这个判断力比会默写某一道题的代码重要得多。 
长河君 · 2026/10/10 16:19:19 · 阅读 1.2k 回文子串与回文子序列：二维DP遍历顺序与中心扩展法详解
开始刷到第四十五天字符串相关的动态规划算是快收尾了。今天这两道题647回文子串和516最长回文子序列放在一起刷其实挺有意思——同样都是“回文”一个要求连续的子串一个允许不连续的子序列解法上的差异和共通点正好能帮人把二维DP的遍历顺序彻底想明白。如果你正在跟代码随想录算法营或者刚刷完编辑距离那一批题这两道可以作为字符串DP的收尾练习如果你是零基础刚起步也不用怕今天的内容我会从最基础的暴力思路讲起把每一步推导掰开来说。1. 把题目拆清楚子串、子序列、回文三个词别混1.1 回文子串与回文子序列的本质差别先看两个词。“回文子串”要求字符在原字符串里是连续的比如abcba里的bcb是回文子串ab cba中间不管怎么切取出来的字符在原串里必须是紧紧挨着的。而“回文子序列”不要求连续只要求保持相对顺序比如bbbab里我们可以隔着字符取bbbb它不连续但确实是回文子序列。这个差别直接决定了算法的形态。连续意味着我们可以枚举每个位置向两边扩张不连续意味着我们要考虑“跳过某个字符”的可能性这就天然指向了区间DP——用dp[i][j]表示从i到j这一段区间的状态通过端点字符是否相等来决定往哪个子区间转移。很多初学者会把两道题混在一起看觉得都是“统计回文”或者“找最长回文”但写代码时就会发现子串题用的是二维布尔数组来标记(i,j)区间是否为回文子序列题用的是二维整数数组来记录区间内的最长回文长度。数据结构选型不同遍历顺序不同初始化策略也不同这些细节串起来才是这两道题的完整考点。1.2 暴力解法到底有多贵为什么要优化先给自己一个直观感受。对于647一个最简单的暴力是枚举所有子串的起点和终点再写一个isPalindrome函数去判断这样枚举起点终点是O(n²)每个子串判断又是O(n)总复杂度O(n³)。字符串长度到100这个方案还勉强能跑但力扣的测试数据一上来超时是必然的。至于516如果枚举所有子序列那就是2的n次方级别压根不是能写出来的算法。所以两道题的第一课都是暴力枚举作为起点用来验证思路没问题但最终解法必须做到O(n²)以内。647的O(n²)解法有两条路一条是中心扩展一条是动态规划516则基本只有动态规划这一条正路中心扩展在这里派不上用场因为子序列允许跳过字符单靠左右指针扩张覆盖不了“中间隔了几个字符再匹配”的情况。这里也回应一个很多人问过的问题为什么两道题都用二维DP因为回文天然是区间属性——s[i..j]是否是回文、s[i..j]的最长回文子序列长度都只和这个闭区间本身有关和区间外面的字符无关。把大区间拆成小区间小区间的答案可以递推出来这就是区间DP的基本盘。2. 647 回文子串中心扩展法和动态规划两条路线都值得写一遍2.1 中心扩展法O(1)空间的漂亮解法先讲中心扩展因为我个人觉得这道题用中心扩展更直观代码也短。思路一句话遍历所有可能的回文中心然后向两边扩张只要左右字符相等就算发现一个回文子串。这里最关键的是中心的数量。一个长度为n的字符串回文中心不只有n个而是2n - 1个。为什么因为回文分两种奇数长度的回文有一个中心字符比如aba的中心是b偶数长度的回文中心在两个字符之间比如abba的中心在b和b中间不是一个具体的字符。所以中心扩展要拆成两种情况分别处理class Solution { public: int countSubstrings(string s) { int n s.size(); int ans 0; for (int i 0; i n; i) { // 奇数长度回文中心是i ans expand(s, i, i); // 偶数长度回文中心在i和i1之间 ans expand(s, i, i 1); } return ans; } int expand(const string s, int left, int right) { int count 0; while (left 0 right s.size() s[left] s[right]) { count; left--; right; } return count; } };我最早学这个写法的时候有个困惑expand(s, i, i)是不是只记了一个回文比如aaa以第二个a为中心扩展会依次发现a、aaa所以一次expand返回的其实是“以这个中心能扩张到的所有回文子串数量”不只是1个。理解这一点就不会在计数时出错了。这个解法的时间复杂度是O(n²)空间复杂度是O(1)不用开二维数组实测在LeetCode 647上表现相当好。很多教科书喜欢拿DP做这道题但面试时如果能先给中心扩展通常会让面试官眼前一亮因为空间上明显优于二维DP。2.2 动态规划法为区间DP打下的地基既然今天的另一道题要用DP647也用DP写一遍正好把二维布尔DP的套路练熟。定义dp[i][j]表示s[i..j]闭区间是否为回文子串是布尔值。递推的核心逻辑是如果s[i] s[j]并且区间长度小于等于3或者dp[i1][j-1]是回文那么dp[i][j]就是回文。为什么长度小于等于3要单独判断因为当j - i 2时比如a、aa、aba去掉首尾后剩下的区间要么是空的要么只有一个字符它们天然是回文不需要依赖dp[i1][j-1]。如果直接去查dp[i1][j-1]在i1 j-1的情况下下标就乱套了。这里有个细节我必须提醒你遍历顺序必须从下往上、从左往右。因为dp[i][j]依赖dp[i1][j-1]也就是左下角的值。如果你按i从0到n-1、j从i到n-1的顺序遍历那么计算dp[0][3]时dp[1][2]还没来得及算查出来就是个错误值。正确做法是让i从大到小j从小到大class Solution { public: int countSubstrings(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n, false)); int ans 0; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j]) { if (j - i 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } if (dp[i][j]) ans; } } return ans; } };很多同学第一次写会漏掉j i这个条件或者把j的起点写成0结果访问了大量j i的无意义位置。其实对角线以下的区域我们根本不用管j从i开始就可以了。两条路线的取舍我个人的建议是笔试或日常刷题用动态规划因为和后续的516能形成方法上的连贯面试手撕用中心扩展因为代码短、空间好、边界处理直观。两种都会写才是这道题的正确打开方式。3. 516 最长回文子序列二维DP里最难的那一类不在递推在初始化3.1 DP定义与递推公式的推倒过程如果说647的DP是二维布尔表的“入门款”516的DP就是二维整数表的“进阶款”。先定义dp[i][j]字符串s[i..j]范围内最长回文子序列的长度。这个定义和647有本质区别——647记录的是“是或不是”516记录的是“有多长”前者是状态判断后者是数值统计。递推公式分两种情况当s[i] s[j]时说明两端字符可以同时收进回文子序列那么dp[i][j] dp[i1][j-1] 2。这里加2是因为首尾两个字符都算上了。当s[i] ! s[j]时说明s[i]和s[j]不可能同时出现在同一个回文子序列的首尾那我们只能二选一要么放弃s[i]看dp[i1][j]要么放弃s[j]看dp[i][j-1]。取两者的最大值。写成代码class Solution { public: int longestPalindromeSubseq(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); for (int i 0; i n; i) dp[i][i] 1; for (int i n - 1; i 0; i--) { for (int j i 1; j n; j) { 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[i][i] 1这一步必须在双重循环之前做好因为单个字符本身就是长度为1的回文子序列。如果你只初始化dp为0那么计算dp[i][i1]这种长度为2的区间时如果s[i] ! s[j]结果会变成0但正确答案应该是1——你至少可以选其中任意一个字符作为长度为1的回文子序列。另一个细节是循环里j从i 1开始因为dp[i][i]已经初始化了不需要在转移里再处理。如果你写成j i在dp[i][i]上套公式当s[i] s[i]时会得到dp[i1][i-1] 2这个区间是非法区间结果就错了。3.2 区间长度的推进顺序决定你代码能不能一次跑对516的遍历顺序比647更容易写错。在647里dp[i][j]依赖dp[i1][j-1]同样是左下角所以需要i倒序、j正序。516除了依赖左下角还依赖左侧和下方即dp[i][j-1]和dp[i1][j]。如果i倒序、j正序这两个依赖也都能在计算dp[i][j]之前得到因为j-1在当前行左侧已经在这一行算过了i1在下一行上一轮外层循环算过了。可如果你把外层i写成正序内层j从i 1开始那么计算dp[i][j]时dp[i1][j-1]和dp[i1][j]都还是初值0递推就变成了纯靠初始化的假结果整张表全是错的。我当时在这道题栽过一次后来想了个笨办法帮助记忆看你的dp表怎么画依赖关系指向哪个方向遍历方向就跟依赖相反。dp[i][j]依赖左下角所以必须从表的右下方往左上方填具体就是一行的j从左往右但行要自下而上。这和二维数组的“行优先”直觉正好相反所以特别容易错。这道题还可以顺带证明一个性质dp[i][j]不会小于dp[i1][j]也不会小于dp[i][j-1]因为区间越大包含的字符越多最长回文子序列长度只可能增加。这个性质保证了当s[i] ! s[j]时取max是安全的不会出现“区间变长反而答案变小”的诡异情况。4. 两题对照数据结构的差异决定了遍历方向的不同4.1 同样是区间DP为什么一个用bool一个用int把647和516的代码放在一起看最直观的差异是dp表的类型。647的dp是vectorvectorbool因为每个区间只需要回答“是不是回文”516的dp是vectorvectorint因为每个区间要回答“最长回文子序列有多长”。类型的差异背后是信息量的差异。647里我们一旦知道dp[i][j]是回文就计数加1不需要继续叠加长度516里我们要把子问题的解“合并”起来合并的操作是加法或取max这要求dp的值本身就保存了数值信息。这也是为什么有些同学会试着用647的DP思路去解516结果发现计数逻辑完全用不上——因为两道题虽然在同一个“回文”主题下但目标函数不同一个是统计个数一个是求解最大值统计问题适合布尔标记最值问题适合数值叠加。4.2 面试时怎么快速决定用哪种解法如果面试官给的是“求回文子串个数”我的第一反应一定是中心扩展法。原因有三个代码量最小出错概率低空间O(1)能体现复杂度意识扩展过程直观方便向面试官解释思路。如果你先用DP写647面试官追问“能不能优化空间”你再改写中心扩展虽然也能圆回来但不如一开始就给出空间更优的方案来得清爽。如果面试官给的是“最长回文子序列长度”那就只能走DP没有中心扩展的捷径。这个时候我会先花三十秒说清楚三件事dp[i][j]的含义、s[i]s[j]和s[i]!s[j]两个分支、i倒序j正序的遍历原因。把这三件事讲明白代码本身反而是最不重要的。从学习顺序上我也建议先看647再看516。647的递推里没有max分支很单纯适合建立“区间DP”的直觉516在647的基础上加入了“放弃一端字符”的转移逻辑理解难度上一个台阶但一旦想通编辑距离类的题目你会顺手很多因为它们同样是在做“匹配成功就加一、匹配失败就在两个子问题里取最优”的事。5. 高频报错与易错点实录这些坑我替大家踩过了5.1 遍历顺序写反是最隐蔽的Bug这类区间DP的for循环顺序写错往往不报编译错误也不报数组越界就是结果不对。我见过太多人拿着for (int i 0; i n; i) for (int j i 1; j n; j)的代码来问为什么输出是1一看就知道是依赖的左下角还没算。这里给你一个“一眼定位”的方法在循环体内临时把dp[i][j]打出来对比手算的小例子bbbab如果第一行第一列是一些莫名其妙的0基本就是遍历方向错了。更快的定位方法是直接检查j i 1那一层斜线的填表顺序——用表格画出来你会发现正确的填法是从右下角出发一层一层往左上角推像剥洋葱一样。5.2 647 DP里的j - i 2到底覆盖了哪些情形很多刚开始写647 DP的同学会纠结这个边界条件到底该取 1还是 2。我们拆开看当j - i 0只有一个字符a回文当j - i 1两个字符aa只要相等就是回文当j - i 2三个字符aba只要首尾相等中间不管是什么都只有一个字符天然回文。所以j - i 2是准确的三种情况全覆盖。如果写成j - i 1长度为3的回文aba就会走dp[i1][j-1]也就是去查dp[1][1]这个值是true结果也能对。但写成 2更安全逻辑也更清晰长度不超过3的区间不需要依赖子区间。建议记住这个结论面试时能直接说出“长度小于等于3的区间一定回文”的原因会让面试官觉得你的边界意识很到位。5.3 516的返回值到底取哪里516的答案在dp[0][n-1]也就是整个字符串区间的最长回文子序列长度。这个位置在表格的右上角是最后填完的一个位置。很多同学会在循环结束后额外扫一遍dp求最大值其实没必要——dp[0][n-1]已经覆盖了全长区间而dp[i][j]随着区间扩大只增不减所以右上角天然是全局最大值。额外扫描不会错但说明你对“区间DP天然满足最优子结构”的理解还差了点火候。另外516有一个初始化的隐藏要求n 1时循环体一次都不进直接返回dp[0][0] 1。这个用例能帮你验证自己的初始化代码是否干净。如果你忘了给dp[i][i]赋值输入a就会返回0这属于最典型的低级错误。5.4 字符串处理题里常见的时间复杂度陷阱写647中心扩展的时候很多人会问“这里不是嵌套了两层循环为什么是O(n²)而不是O(n³)”因为内层while虽然可能扩展很长但在每个中心上扩展的总步数和字符串长度相关对2n - 1个中心来说最坏情况的扩展总长度是O(n)平摊到每次扩展还是O(n)。具体来说所有中心扩展步数之和的量级是O(n²)比如全aaaa这种情况下每个中心扩展步长接近n/2但乘上中心数仍是n²级别。想象一个长方形横轴是中心序号纵轴是扩展半径所有小矩形的总面积不会超过n²这就是O(n²)的直观来源。而516的DP是标准的双重循环每一对(i, j)都做常数次操作所以也是O(n²)时间但空间是O(n²)。如果面试官继续追问空间优化516理论上可以优化到O(n)因为每一行只依赖下一行和当前行的前一个位置可以用滚动数组但面试通常不会强制要求因为代码复杂度会上升不少。6. 实操心法这道题之后你对二维DP的理解会不一样6.1 用一个自测用例串起所有边界我自己刷完这两道题固定用一组用例来验证代码是否正确。647用aaa期望答案是6a出现3次aa出现2次aaa出现1次3216。516用bbbab期望答案是4因为最长回文子序列是bbbb再用cbbd期望答案是2因为bb或者c长度为1都可以取。如果这些用例一次通过代码基本就没问题。再补一个细节647的aaa其实是中心扩展法最好的测试用例因为奇数中心和偶数中心都很多能同时检验两种中心类型。如果代码输出不是6通常问题出在中心遍历范围上——比如只遍历了奇数中心漏掉了偶数中心输出会少一半。6.2 为什么说这两道题是字符串DP的分水岭在代码随想录算法营的进度里第45天意味着你已经见过不少DP题型了背包、打家劫舍、股票问题、编辑距离。回文这两题看似在“字符串”里打转实际上把区间DP的核心思想完整曝光了一遍区间定义、端点匹配与放弃、子区间依赖、遍历方向、初始化边界。学会了这套东西很多经典面试题都会迎刃而解。比如131. 分割回文串需要先预处理任意子串是否是回文本质上就是647的DP表又比如1143. 最长公共子序列它的dp递推和516长得几乎一样区别只是两个字符串和两个指针的移动策略。所以今天这两道题不是终点而是给后面这些“更长的串”打底。6.3 最后分享一个刷题节奏上的体会这一天两道题看起来不多但加上复盘和写笔记我一般会预留一个半小时。第一遍先不看题解尝试中心扩展解647如果DP能自己推出来就更好516建议哪怕写不出来也要先把自己的递推思路写到纸上卡住了再看题解——这比直接抄答案记住得更牢。今天这两道题最值得收藏的一句话是回文子串用中心扩展回文子序列用区间DP。当你看到题目里带着“子序列”三个字基本上就和连续算法说再见了接下来要做的第一件事一定是思考能不能用区间DP建模。这个判断力比会默写某一道题的代码重要得多。