1. 回文类问题的整体设计与思路拆解
刷到算法训练营第56天，动态规划这一块只剩最后两题：回文子串和最长回文子序列。很多人前面背包、打家劫舍、股票系列都啃下来了，偏偏卡在这两道上，倒不是题多难，而是它们引入了一个此前没怎么正面用过的模型——区间动态规划。状态不再是“前 i 个元素”，而是“从 i 到 j 这一段”，遍历顺序也不是从 0 到 n，而是从右下角往左上角推。这个转向如果不理解透彻，写出来的代码往往“逻辑看着没问题，答案是错的”，而且错得很隐蔽。
这一篇我准备把这两道题掰开揉碎讲清楚：回文子串怎么从中心扩展法过渡到区间 DP，最长回文子序列的状态转移为什么长成那样，以及动态规划这个大板块收尾时我自己沉淀下来的复盘方法。适合已经会写基础 DP、但一碰到二维区间就发怵的朋友，也适合那些“代码能背下来但换道题就懵”的读者。所有推导我都会给出手推表格和可运行的代码，Java 和 Python 两种，挑顺手的看。
1.1 为什么回文问题天然长在“区间”上
先想清楚一个本质问题：回文的定义是什么？是“一个字符串正着读和反着读一样”。这个定义本身就自带对称性和区间边界两个属性。判断s[i..j]是不是回文，你没法只依赖s[0..i-1]的信息，因为回文的成立与否完全取决于两端字符是否相等，再往里收缩一层。这种“由外层决定内层、内层结果反哺外层”的结构，正是区间 DP 最擅长的形态。
对比一下线性 DP 的典型代表——最长递增子序列。它的状态是dp[i]表示“以 i 结尾的 LIS 长度”，因为你只需要知道“前一个接谁”，是从左往右单向生长。而回文是双向往中间生长的，dp[i]这个只有右端点的状态压根描述不了左边界在哪儿。你必须把两个端点都编码进状态里，dp[i][j]就成了唯一合理的载体。
理解这一点的价值在于：下次看到题目里出现“两端对称”“区间内最优”“从中间往外扩或者从外往里收”这类描述时，你的第一反应应该是二维区间 DP，而不是硬套一维。这是一个模式识别问题，识别对了，后面写代码就是机械劳动。
1.2 三种主力解法怎么选
回文子串这道题，能打的解法至少有三种，各有各的适用面。我把它们的特性列成一张表，方便你在不同场景下做取舍：
| 解法 | 时间复杂度 | 空间复杂度 | 代码长度 | 适用场景 |
|---|---|---|---|---|
| 暴力枚举 + 判断 | O(n³) | O(1) | 极短 | 只用来验证答案、n 极小的场景 |
| 中心扩展 | O(n²) | O(1) | 短 | 面试手写首选，不易写错 |
| 区间 DP | O(n²) | O(n²)/O(n) | 中等 | 需要复用 dp 表的变形题 |
| 字符串哈希 + 二分 | O(n log n) | O(n) | 中偏长 | 追求理论复杂度、题目有多次询问 |
| 马拉车（Manacher） | O(n) | O(n) | 长 | 竞赛场景、对常数和复杂度极敏感 |
这里有一个很实用的判断：如果面试官只让你求回文子串的个数或者最长回文子串，中心扩展就够了，写起来快、bug 少，还自带 O(1) 空间。但如果后面的变形题需要用到“某个子区间是不是回文”这个信息（比如分割回文串、回文划分的最少次数），那你就必须老老实实把 DP 表建出来，因为那张表本身就是后续题目的输入。
我在训练营里踩过一次坑：先用中心扩展秒了回文子串，紧接着下一题是“分割回文串 II”，要求最少分割次数，我下意识又想用中心扩展，结果发现每次判断子串都要重新扫一遍，复杂度直接炸到 O(n³)。后来把区间 DP 表建好，dp[i][j]这个布尔矩阵直接喂给下一层，一次遍历就出结果。这次教训让我养成了一个习惯：做题前先扫一眼这一组题有没有关联，如果有关联，优先选那个“能把中间结果留下来”的解法。
1.3 状态定义的两种思路：以 i 结尾 vs 以 [i, j] 为区间
动态规划最难的一步永远是状态定义，这两道题正好是两种思路的对照样本。
回文子串的状态是dp[i][j] = s[i..j] 是否为回文，值是布尔型或者计数型。这个定义很直白，但初学者容易卡在“为什么不能定义成dp[i]表示以 i 结尾的回文子串个数”——答案是能，但没法转移，因为你不知道前面那个对称位置在哪。
最长回文子序列的状态是dp[i][j] = s[i..j] 中最长回文子序列的长度。注意这里词儿变了：子串要求连续，子序列不要求连续。这个差别导致转移方程完全不同，也是这两道题放在同一天讲的核心用意——同样的区间定义，因为“连续约束”的有无，转移逻辑会分化成两条路线。
我个人的经验是，定义区间状态时有三个动作要做全：第一，明确dp[i][j]的语义里到底含不含端点（是闭区间还是半开区间，大多数人用闭区间，写的时候注意j >= i）；第二，明确i和j的相对关系，永远只填i <= j的那半张表；第三，明确最终答案落在哪个格子上（是dp[0][n-1]还是全表最大值）。这三件事定死了，代码基本就是照着抄。
2. 回文子串：从中心扩展到区间 DP 的完整推演
2.1 中心扩展：先用最笨的办法把答案拿到手
中心扩展的思路特别自然：一个回文串一定有一个“中心”。长度是奇数时，中心是单个字符；长度是偶数时，中心是两个相邻字符之间的空隙。于是我们从每一个可能的中心出发，向两边同时扩张，只要两边字符相等就继续，一旦不等就停下。
def count_substrings_expand(s: str) -> int: n = len(s) total = 0 def expand(left: int, right: int) -> int: cnt = 0 while left >= 0 and right < n and s[left] == s[right]: cnt += 1 left -= 1 right += 1 return cnt for center in range(n): total += expand(center, center) # 奇数长度，中心是单个字符 total += expand(center, center + 1) # 偶数长度，中心是空隙 return total这段代码的复杂度是 O(n²)，空间 O(1)，实测跑 n=1000 的随机串毫无压力。它最大的优势是不需要想清楚遍历顺序，因为扩张本身就是按长度自然递增的，天然满足依赖关系。
不过这里有个细节值得说：expand里我返回的是个数而不是最大长度。因为回文子串这道题求的是“不同回文子串的数目”，从同一个中心每扩张一步就产生一个新的、不同起止位置的回文串，所以计数就是扩张的次数。如果你求的是最长回文子串，那就把cnt += 1换成记录right - left - 1的最大值。同一个框架换个返回值就完成题目切换。
注意：中心扩展在字符串全部相同时会退化成 O(n²) 的最坏情况，这正是它复杂度上界达不到 O(n) 的原因。如果题目数据量给到 10⁵ 级别，就得上马拉车了，日常刷题基本用不到。
2.2 区间 DP 的状态定义与转移推导
现在换成 DP 视角。定义dp[i][j]表示s[i..j]这段是否回文，布尔值。接下来推导转移。
判断s[i..j]，第一步一定看两端：s[i]和s[j]。如果它俩不相等，那这个区间铁定不是回文，dp[i][j] = false，没有第二种可能。如果它俩相等，那结果取决于去掉两端后的s[i+1..j-1]是不是回文——这就是转移的核心。
但这里有个边界要处理：当j - i <= 1时，也就是区间长度是 1 或 2，去掉两端后中间什么都不剩或者只剩单个字符，这两种情况只要两端相等就一定是回文。长度 1 天然回文，长度 2 两端相等即回文。所以完整转移是：
if s[i] != s[j]: dp[i][j] = false else: if j - i <= 1: dp[i][j] = true else: dp[i][j] = dp[i+1][j-1]很多人第一次写会漏掉j - i <= 1这个分支，导致长度 1 和 2 的区间去访问dp[i+1][j-1]越界或者拿到脏值。这个坑我见过太多次了。
顺便说明一下为什么不用考虑 “s[i] == s[j]但中间不是回文” 的情况——这种情况dp[i+1][j-1]已经是 false 了，转移自动覆盖，不需要额外分支。
2.3 遍历顺序：这一步写反了整张表都是错的
这是区间 DP 最要命的地方。看转移式：dp[i][j]依赖dp[i+1][j-1]。注意这个依赖的方向——行号更大（i+1），列号更小（j-1）。也就是说，它依赖的是自己“左下角”那一格。
那填表顺序就必须保证：填到dp[i][j]时，dp[i+1][j-1]已经算好了。满足这个条件的顺序是：i 从 n-1 递减到 0，j 从 i 递增到 n-1。
我把它画成文字版的表格感受一下（以 n=4 为例，X 表示 i>j 的无效区）：
j=0 j=1 j=2 j=3 i=0 (1) (2) (4) (7) i=1 X (3) (5) (8) i=2 X X (6) (9) i=3 X X X (10)括号里是填表顺序。你会看到它是一列一列斜着往右上走的：先填(0,0)，再(0,1)、(1,1)，再(0,2)、(1,2)、(2,2)……这种顺序保证了任何一个格子被填的时候，它左下角那格一定已经有值了。
换个说法：如果你按i从 0 到 n-1、j从 i 到 n-1 的顺序填，那么填dp[0][3]时它需要的dp[1][2]还没算，拿到的就是初始化值 false，结果全错。这种错误特别阴险，小样例可能碰巧过，大样例直接崩。
一个口诀记法：区间 DP 想让内层先算好，外层就必须倒着走。因为内层区间比外层短，区间长度是从小到大推出的，而
i倒序恰好对应长度从小到大。
2.4 完整代码与逐行注释
Java 版本，我平时刷题主要用这个：
class Solution { public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int count = 0; // i 从后往前，保证 dp[i+1][j-1] 先于 dp[i][j] 计算 for (int i = n - 1; i >= 0; i--) { // j 从 i 开始，只填 i <= j 的上三角 for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i <= 1) { dp[i][j] = true; // 长度 1 或 2 } else { dp[i][j] = dp[i + 1][j - 1]; // 依赖左下角 } } if (dp[i][j]) count++; } } return count; } }Python 版本：
def count_substrings_dp(s: str) -> int: n = len(s) dp = [[False] * n for _ in range(n)] count = 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 count += 1 return countPython 这版把条件用and串起来了，看起来更紧凑。注意or的短路特性——j - i <= 1成立时，后面的dp[i+1][j-1]根本不会被求值，所以不会越界。这个技巧在笔试手写场景下很好用，但面试时我还是建议写成显式 if-else，可读性更好，也方便面试官跟进你的思路。
2.5 一维压缩：省的不只是内存，是思维方式的切换
如果你观察转移式dp[i][j] = dp[i+1][j-1]，会发现第 i 行只依赖第 i+1 行。理论上可以把二维压成一维。但这里有陷阱——不是简单地把行滚掉就行，j 的遍历方向必须跟着改。
先看错误的写法：
// 错误示范：j 正序 + 一维滚动 boolean[] dp = new boolean[n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[j - 1])) { dp[j] = true; } else { dp[j] = false; } } }问题出在dp[j-1]。当 j 正序遍历时，dp[j-1]在本轮i里已经被更新过了，它代表的是dp[i][j-1]（本轮新值），而我们真正需要的是dp[i+1][j-1]（上一轮的旧值）。语义错位，结果自然错。
修正方案有两种。一种是 j 倒序，让dp[j-1]还没被本轮污染：
public int countSubstrings1D(String s) { int n = s.length(); boolean[] dp = new boolean[n]; int count = 0; for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= i; j--) { if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[j - 1])) { dp[j] = true; count++; } else { dp[j] = false; } } } return count; }另一种是 j 依然正序，但用一个临时变量把上一行的值提前存下来（后面讲最长回文子序列时会用这招，因为那题的 j 正序更好写）。两种方式本质等价，取哪个看你顺手。
实操心得：一维压缩在比赛里确实能省内存，但除非数据规模真的卡你，否则我建议先写二维版。二维表好调试、好打印、好对着手推表校验。等二维版 AC 之后再压一维，出问题也知道是压缩那一步引入的，排查范围小很多。
3. 最长回文子序列：区间 DP 的标准模板
3.1 子串与子序列只差一个字，转移方程差一整段
先把概念钉死：子串必须连续，子序列不要求连续。这个差别不是文字游戏，它直接决定了两道题的转移方程结构。
拿"bbbab"举例。最长回文子串是"bbb"，长度 3；最长回文子序列是"bbbb"，长度 4——因为我们可以把下标 0、1、2、3 的四个 b 挑出来，跳过中间的 a，拼成"bbbb"。子序列允许“跳跃”，于是问题从“找一段连续的对称区间”变成了“在区间内挑出一个最优的对称子集”，自由度大了一档。
这个自由度体现在 DP 上，就是转移里多了一个max。子串只有“是/不是”两态，容不下最优性；子序列要求最优值，所以转移里要比较“丢掉左端”和“丢掉右端”哪个更划算。
3.2 转移方程的推导过程
状态：dp[i][j]表示s[i..j]范围内最长回文子序列的长度。
考虑两端字符s[i]和s[j]：
情况一，s[i] == s[j]。那这两个字符可以直接放进回文序列的两端，中间部分继续取s[i+1..j-1]的最优解。所以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])。前者是放弃s[i]，后者是放弃s[j]。
这个推导里有个容易忽视的点：s[i] != s[j]时，能不能只写max(dp[i+1][j], dp[i][j-1])？会不会漏掉某种更优组合？答案是不会。因为任何合法的回文子序列，如果它同时包含了s[i]和s[j]作为两端，那必然要求s[i] == s[j]，与前提矛盾；所以它一定不含s[i]或者不含s[j]，两种情况被后两项完整覆盖。这是区间 DP 里典型的完备性论证，面试时能讲清楚这一句，通常就是加分项。
3.3 初始化、边界与返回值
初始化：dp[i][i] = 1，因为单个字符本身就是长度 1 的回文子序列。所有i > j的位置保持 0（逻辑上表示空区间，长度为 0），这个 0 在dp[i+1][j-1]中会被用到——比如j = i+1时，dp[i+1][i]就是空区间，取 0，然后+2得到 2，正好是"aa"这类长度为 2 的回文。
返回值：dp[0][n-1]，整个串的最优解。
遍历顺序和上一题一致：i从n-1递减到0，j从i+1递增到n-1。注意这里j从i+1开始就行，因为j == i的位置已经初始化过了。
3.4 代码实现与滚动数组的覆盖问题
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; 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.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return n == 0 ? 0 : dp[0][n - 1]; } }一维压缩版本要注意的地方更多，因为同时依赖了三个位置：dp[i+1][j-1]（左上）、dp[i+1][j]（上方，旧值）、dp[i][j-1]（左方，新值）。上一题只需要区分旧值和新值，这题三个方向全占。
public int longestPalindromeSubseq1D(String s) { int n = s.length(); int[] dp = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { int pre = 0; // 相当于 dp[i+1][i]，空区间为 0 for (int j = i; j < n; j++) { int temp = dp[j]; // 先存下旧的 dp[i+1][j] if (i == j) { dp[j] = 1; } else if (s.charAt(i) == s.charAt(j)) { dp[j] = pre + 2; // pre 就是 dp[i+1][j-1] } else { dp[j] = Math.max(dp[j], dp[j - 1]); // dp[j] 此刻还是旧值 dp[i+1][j] // dp[j-1] 是本轮新值 dp[i][j-1] } pre = temp; // 更新 pre，供下一次 j+1 使用 } } return dp[n - 1]; }pre这个变量的作用是精确复刻dp[i+1][j-1]。因为j每次前进一步，j-1对应的“上一行”值就是刚才那一轮迭代里被覆盖掉的dp[j]。如果你漏了pre = temp这一行，pre会一直是 0，所有s[i]==s[j]的分支都会少加 2，答案偏小且非常难查。
注意：一维版本里
dp数组开的是n长度、下标对j，第 0 位在j循环开始前是上一行的旧值，用它算出新值后马上覆盖。这种“边读边写”的滚动方式在区间 DP 里很常见，但一定要在纸上画两轮，确认自己清楚每个位置此刻到底是旧值还是新值。
3.5 一道题的三种马甲：插入、删除、构造
最长回文子序列是这一族的母题，很多题都是它的变形，本质是同一个 DP 换个问法。我把常见的三种整理出来：
| 变形题问法 | 与母题的关系 | 关键转换 |
|---|---|---|
| 让字符串变成回文的最少插入次数 | 插入的是“补对称”的字符 | n - 最长回文子序列长度 |
| 让字符串变成回文的最少删除次数 | 删掉的是“不成对”的字符 | n - 最长回文子序列长度 |
| 构造最长回文串（可任意排列） | 可以用所有字符，只需成对 | 统计每种字符出现次数，偶数全用，奇数减一用 |
第一、第二种转换值得展开说一句：为什么最少的插入/删除次数恰好等于n - LPS？因为一个长度为L的回文子序列，覆盖了原串中的L个字符，剩下n - L个字符就是“多余”的，要么删掉它们，要么为每个补一个对称字符。下界和上界都能对上，所以这就是最优。
第三种“构造最长回文串”稍微特殊，它不用区间 DP，直接贪心+计数就够——因为字符可以随便重排，位置约束消失了。这也提醒我们：动态规划的适用范围严格绑定在“有顺序约束”这个前提上，一旦约束消失，贪心或者计数往往更简单。
4. 实操过程记录：我是怎么把这两题一次写对的
4.1 手推 “aabaa” 的完整 dp 表
我有个改不掉的习惯：写二维 DP 之前，先用一个小样例把表手推一遍，推完再动键盘。这个动作花两三分钟，但能省掉后面半小时的调试。
先看回文子串的布尔表，s = "aabaa"，下标 0~4。填表顺序是从右下角往左上角走：
| i\j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | T | T | F | F | T |
| 1 | - | T | F | T | F |
| 2 | - | - | T | F | F |
| 3 | - | - | - | T | T |
| 4 | - | - | - | - | T |
逐格核对一下关键位置：dp[0][4]，两端都是a，长度 4 > 1，看dp[1][3]，也就是"aba"，是回文，所以 T；dp[1][3]两端都是a，长度 2 > 1，看dp[2][2]是 T，所以 T；dp[0][3]两端a和a相等，看dp[1][2]，"ab"不是回文，所以 F。数一下 T 的个数：第一行 3 个，第二行 2 个，第三行 1 个，第四行 2 个，第五行 1 个，合计 9 个。回文子串就是 5 个单字符 +aa×2 +aba+aabaa= 9，对上了。
再看最长回文子序列的整数表：
| i\j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 2 | 3 | 5 |
| 1 | - | 1 | 1 | 3 | 3 |
| 2 | - | - | 1 | 1 | 2 |
| 3 | - | - | - | 1 | 2 |
| 4 | - | - | - | - | 1 |
重点核对dp[0][4]：两端a相等，取dp[1][3] + 2 = 3 + 2 = 5。再看一个不等的情况dp[0][2]：s[0]='a'，s[2]='b'，不等，取max(dp[1][2], dp[0][1]) = max(1, 2) = 2。逻辑自洽。
手推的价值在于，你能在填表过程中实实在在感受到“依赖左下角”这个方向。光看代码是感受不到的，等到自己动手填，你会自然地意识到“哦我得先算短区间”，遍历顺序就不再是死记硬背的东西。
4.2 打印 dp 表的调试技巧
写完之后如果答案不对，别急着改逻辑，先把表打出来看看哪一格不对劲。Java 版本可以加一段：
// 调试用：打印整张 dp 表 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(dp[i][j] + "\t"); } System.out.println(); }Python 更方便，直接print(*dp, sep='\n')。
打印之后拿你自己手推的表逐格对比，第一个出现差异的格子就是 bug 的位置。这个方法比单步调试快得多，因为 DP 的错误往往是“某几格算错”而不是“全错”，肉眼比对表格的效率远高于打断点。
我在训练营里见过一个同学，他的表里dp[1][3]是 false，可正确答案应该是 true。定位到这一格，一看代码发现外层i是正序遍历的，填dp[1][3]时dp[2][2]还没算。就这么一行循环方向的问题，他找了两个小时。如果早点打表，五分钟就定位了。
4.3 我常用的边界用例清单
算法题本地测，光靠题目给的样例远远不够。我总结了一套专门针对回文类题目的用例集，每次写完都跑一遍：
| 用例 | 预期（回文子串数 / LPS 长度） | 考察点 |
|---|---|---|
"a" | 1 / 1 | 单字符最小值 |
"" | 0 / 0 | 空串，注意数组越界 |
"aa" | 3 / 2 | 长度为 2 的偶数回文 |
"ab" | 2 / 1 | 两字符不相等 |
"abc" | 3 / 1 | 完全无回文 |
"aaa" | 6 / 3 | 全同字符，考验计数是否会重复 |
"abba" | 6 / 4 | 偶数长度整体回文 |
"aaaaa" | 15 / 5 | 长串全同，检查复杂度是否退化 |
"aaa"这个用例特别关键。它同时能测出两种错误：一是计数的时候有没有重复计入同一个区间，二是 DP 表里子区间的依赖有没有算对。"aaaaa"则用来确认算法在极端情况下不会因为常数问题超时。
实操心得：本地测的时候，如果题目允许暴力解，就顺手写一个 O(n³) 的暴力版本当对拍器。随机生成长度 1 到 8 的字符串，两个函数各跑一遍比结果，跑个几百组，基本上覆盖度就差不多了。这个方法虽然土，但抓边界 bug 的效率极高。
5. 动态规划板块的整体复盘
5.1 五步法：不是流程，是排序
动态规划被讲烂了那五步——确定状态、推导转移、初始化、确定遍历顺序、举例推导。但很多人照着做还是不会，问题在于把这五步当成流水线了。实际上这五步里，第一步和第二步是互相咬合的：状态定义决定了转移能长成什么样，转移的依赖方向又反过来约束状态该怎么切分。你经常要在两者之间来回跳，定义一版、推个转移、发现推不通、回来改状态。
真实的思考顺序更像是这样：先问“答案取决于哪些量”，把这些量塞进状态里去试；再问“最后一步的决策是什么”，从决策反推转移；转移推不通就回头换状态定义。这是一个收敛的过程，不是线性执行的过程。
举个这两天的例子。回文子串那道题，我第一反应是想定义dp[i]为“以 i 结尾的回文子串个数”，推到一半发现没法转移——因为要知道新增了多少个以 i 结尾的回文串，必须知道前面每个 j 到 i 的子串是不是回文，这不就退化成二维了吗。于是回头改成dp[i][j]，一次推通。这个过程只花了三十秒，但它体现的就是“状态跟着转移走”的真实节奏。
5.2 题型分类图谱
刷完整套动态规划，我习惯按“状态维度 + 依赖结构”来归类，这样遇到新题能快速定位到相近模型：
| 类别 | 代表题 | 状态特征 | 典型复杂度 |
|---|---|---|---|
| 线性 DP | 爬楼梯、打家劫舍、最大子数组和 | 一维，从前往后 | O(n) ~ O(n²) |
| 背包 DP | 01 背包、完全背包、多重背包 | 二维压缩到一维，容量维度倒序 | O(n·W) |
| 序列 DP | 最长递增子序列、最长公共子序列 | 双序列双指针 | O(n²) 或 O(n log n) |
| 区间 DP | 回文子串、最长回文子序列、戳气球 | 双端点，从短区间推长区间 | O(n²) ~ O(n³) |
| 树形 DP | 打家劫舍 III、树的最大路径和 | 后序遍历，合并子树信息 | O(n) |
| 状态压缩 DP | 旅行商、棋盘覆盖 | 二进制位表示集合 | O(2ⁿ·n) |
| 数位 DP | 统计满足条件的数字个数 | 从高位到低位，记忆化 | O(位数·状态数) |
这张表的用处是给新题定位。看到“区间内最优”，往区间 DP 靠；看到“选或不选、总容量有限”，往背包靠；看到“两棵子树的信息合并”，往树形靠。定位准了，状态定义和转移式至少能猜个七七八八。
5.3 状态定义的四个抓手
回过头看，我定义状态时最常用的是这四个抓手，按优先级排：
第一抓“最后一步”。想清楚最优解的最后一次决策是什么。回文子序列里，最后一步就是“两端字符相等要不要用”——用，消耗掉两端；不用，丢一边。把这个决策写清楚，转移就出来了。
第二抓“约束量”。题目里限制了什么的量，就往状态里塞。背包塞容量，股票塞“持有/未持有”，区间题塞两个端点。
第三抓“对称性”。如果问题有对称结构（回文、括号、区间合并），优先考虑双端点状态。这类问题的转移往往关于中心对称或者关于区间长度递推。
第四抓“能不能滚掉一维”。定义的时候顺手看一眼依赖方向，如果只依赖相邻一两行，那就有压缩空间。这一点不影响正确性，但影响你对自己代码的理解深度。
5.4 遍历顺序与依赖方向对照表
区间 DP 的顺序问题值得单独拎出来，因为它是最容易出错的地方。我总结成一张对照表：
| 依赖关系 | 含义 | 遍历顺序 | 例子 |
|---|---|---|---|
dp[i][j]←dp[i+1][j-1] | 依赖左下方 | i 倒序，j 正序 | 回文子串 |
dp[i][j]←dp[i+1][j]、dp[i][j-1] | 依赖下方和左方 | i 倒序，j 正序 | 最长回文子序列 |
dp[i][j]←dp[i-1][j-1]、dp[i][j-1] | 依赖左上方和左方 | i 正序，j 正序 | 最长公共子序列 |
| 背包一维 | 依赖本行旧值 | 容量倒序 | 01 背包 |
| 完全背包一维 | 依赖本行新值 | 容量正序 | 完全背包 |
规律其实很清楚：如果当前格子依赖的格子还没被算到，顺序就错了。所以判断方法很简单——拿起笔在格子上画个箭头，从依赖格指向被依赖格，然后找一个拓扑序，那就是正确的遍历顺序。这个方法比背口诀可靠得多，换任何题都能用。
5.5 空间优化的三个前提
空间压缩是一把双刃剑，用对了能让代码更紧凑，用错了就是长时间调不出来的 bug。我给自己定了三个前提，三条都满足才动压缩：
前提一，确认依赖只涉及“上一轮”和“本轮”。如果依赖了上上轮的某个值，一维数组存不下，需要用两个数组或者额外变量暂存。最长回文子序列里用pre就是为了这个。
前提二，先写对二维版并 AC。这一条是纪律问题。二维版通过之后再压，出问题你就知道是压缩引入的，因为主逻辑已经验证过。反过来先写一维，一旦答案错，你根本分不清是转移推错了还是滚动写错了。
前提三，把“读旧值、写新值”的顺序在纸上标一遍。对于每个用到的变量，明确它此刻是旧值还是新值，标完了再写。最长回文子序列那个dp[j]在max里用的是旧值、在赋值后变成新值，这种“同一格既是读又是写”的情况，不提前标清楚很容易写反。
6. 常见问题与排查技巧实录
6.1 问题速查表
这两道题错误类型相对固定，我整理了一份速查表，遇到 WA 的时候按顺序过一遍：
| 现象 | 最可能的原因 | 排查动作 |
|---|---|---|
| 全部返回 1 或 0 | 初始化没做，或者遍历方向反了，转移从未生效 | 打印 dp 表，看是否只有对角线有值 |
| 小样例过、大样例错 | 依赖顺序问题，短区间用到了未计算的值 | 在转移前所有依赖格打日志，检查是否初始值 |
| 回文子串计数偏大 | 重复统计，或j - i <= 1分支漏判断 | 检查是否对每个 i,j 只计一次 |
| LPS 结果比预期小 2 | +2分支没进，或者pre没更新 | 检查s[i]==s[j]分支是否真的走到 |
| 一维版错、二维版对 | 滚动时旧值被覆盖 | 逐格标注旧值/新值来源 |
| 空串报错 | 没处理 n=0 | 提前返回 0 |
| 超时 | 用了 O(n³) 暴力，或者字符串全同导致中心扩展退化 | 换区间 DP 或检查复杂度 |
6.2 三个“看着对但过不了”的写法
第一个坑：外循环 i 正序。这是我见过最高频的错误。代码逻辑一个字都没错，就是for (int i = 0; i < n; i++)写成了正序，结果dp[i][j]依赖的dp[i+1][j-1]永远是初始值。更麻烦的是，如果初始值恰好对某些小样例给出正确答案，你会以为代码没问题，一直找别的地方。建议养成一个习惯：写完区间 DP，第一件事就是把 i 循环的方向单独检查一遍。
第二个坑：j从 0 开始。有些人为了“保险”，让 j 从 0 开始跑，这会在i > j的区域填上无意义的值，进而污染后续正确区域的依赖。区间 DP 必须严格只填上三角，j从i开始。
第三个坑：LPS 里用i == j判断代替初始化。有人图省事，在双重循环里用if (i == j) dp[i][j] = 1代替外层的初始化，然后让 j 从 i 开始循环。这个写法本身可行，但如果你同时做了一维压缩，i == j时pre应该被置为 0，很多人忘了这一步，导致下一轮j = i+1的时候用了错误的pre。初始化写在循环外，比揉在循环里清晰十倍。
6.3 时间分配的一些经验
最后说点非技术的东西。这类二维 DP 题在笔试里的时间分配，我的做法是：读题三分钟判断类型，手推五分钟确认状态和顺序，写代码十分钟，本地测五分钟，剩下时间留给别的题。如果十五分钟内推不出转移方程，那就先写一个暴力版本保底，暴力能过部分用例，总比空着强。
面试场景下节奏不一样。面试官更看你推导的过程而不是最后的代码，所以要边写边说：先说明状态定义，再解释转移为什么是这个形式，再把遍历顺序的理由讲出来。特别是遍历顺序这一段，主动解释“因为依赖左下角所以 i 要倒序”，这个细节能直接体现你是真的理解而不是背模板。我在模拟面试里遇到过这种情况，代码写得磕磕绊绊，但把依赖方向讲清楚了，评价依然不低。
这两道题作为动态规划板块的收尾挺合适——它们把“状态定义怎么选”“遍历顺序怎么定”“空间怎么压”这三个贯穿整个 DP 板块的通用问题，集中演示了一遍。回文问题我现在的处理方式是：先想区间，确认转移依赖，画箭头定顺序，最后才动键盘。这个流程走顺了之后，类似结构的题（戳气球、括号匹配、石子合并）基本能套着用。唯一需要提醒的是，别把区间 DP 当成万能钥匙，前面那几类线性、背包、序列的题，硬套区间反而绕远路，判断类型那一步永远比写代码更重要。
