开始刷到第四十五天，字符串相关的动态规划算是快收尾了。今天这两道题，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和i+1之间 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打下的地基
既然今天的另一道题要用DP，647也用DP写一遍，正好把二维布尔DP的套路练熟。
定义dp[i][j]表示s[i..j]（闭区间）是否为回文子串，是布尔值。递推的核心逻辑是：如果s[i] == s[j]，并且区间长度小于等于3，或者dp[i+1][j-1]是回文，那么dp[i][j]就是回文。
为什么长度小于等于3要单独判断？因为当j - i <= 2时，比如"a"、"aa"、"aba"，去掉首尾后剩下的区间要么是空的，要么只有一个字符，它们天然是回文，不需要依赖dp[i+1][j-1]。如果直接去查dp[i+1][j-1]，在i+1 > j-1的情况下下标就乱套了。
这里有个细节我必须提醒你：遍历顺序必须从下往上、从左往右。因为dp[i][j]依赖dp[i+1][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(); vector<vector<bool>> dp(n, vector<bool>(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[i+1][j-1] + 2。这里加2是因为首尾两个字符都算上了。 - 当
s[i] != s[j]时，说明s[i]和s[j]不可能同时出现在同一个回文子序列的首尾，那我们只能二选一：要么放弃s[i]，看dp[i+1][j]；要么放弃s[j]，看dp[i][j-1]。取两者的最大值。
写成代码：
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(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][i+1]这种长度为2的区间时，如果s[i] != s[j]，结果会变成0，但正确答案应该是1——你至少可以选其中任意一个字符作为长度为1的回文子序列。
另一个细节是循环里j从i + 1开始，因为dp[i][i]已经初始化了，不需要在转移里再处理。如果你写成j = i，在dp[i][i]上套公式，当s[i] == s[i]时会得到dp[i+1][i-1] + 2，这个区间是非法区间，结果就错了。
3.2 区间长度的推进顺序，决定你代码能不能一次跑对
516的遍历顺序比647更容易写错。在647里，dp[i][j]依赖dp[i+1][j-1]，同样是左下角，所以需要i倒序、j正序。516除了依赖左下角，还依赖左侧和下方，即dp[i][j-1]和dp[i+1][j]。如果i倒序、j正序，这两个依赖也都能在计算dp[i][j]之前得到，因为j-1在当前行左侧（已经在这一行算过了），i+1在下一行（上一轮外层循环算过了）。
可如果你把外层i写成正序，内层j从i + 1开始，那么计算dp[i][j]时，dp[i+1][j-1]和dp[i+1][j]都还是初值0，递推就变成了纯靠初始化的假结果，整张表全是错的。
我当时在这道题栽过一次，后来想了个笨办法帮助记忆：看你的dp表怎么画，依赖关系指向哪个方向，遍历方向就跟依赖相反。dp[i][j]依赖左下角，所以必须从表的右下方往左上方填；具体就是一行的j从左往右，但行要自下而上。这和二维数组的“行优先”直觉正好相反，所以特别容易错。
这道题还可以顺带证明一个性质：dp[i][j]不会小于dp[i+1][j]也不会小于dp[i][j-1]，因为区间越大包含的字符越多，最长回文子序列长度只可能增加。这个性质保证了当s[i] != s[j]时取max是安全的，不会出现“区间变长反而答案变小”的诡异情况。
4. 两题对照：数据结构的差异，决定了遍历方向的不同
4.1 同样是区间DP，为什么一个用bool一个用int
把647和516的代码放在一起看，最直观的差异是dp表的类型。647的dp是vector<vector<bool>>，因为每个区间只需要回答“是不是回文”；516的dp是vector<vector<int>>，因为每个区间要回答“最长回文子序列有多长”。
类型的差异背后是信息量的差异。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[i+1][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"，期望答案是6："a"出现3次，"aa"出现2次，"aaa"出现1次，3+2+1=6。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建模。这个判断力，比会默写某一道题的代码重要得多。
