第一次看到LeetCode 730这道题的时候，我的第一反应是“这题怎么又是Hard”。再仔细读两遍，发现它把三个很容易让人头大的点揉在了一起：子序列、回文、去重。单独看每个词都没那么可怕，但是组合起来就成了经典的区间DP难题。题目给一个字符串s，要求返回所有不同的非空回文子序列的数量，结果对1e9+7取模。所谓“不同”，指的是内容不同，比如"aaa"这个串里，回文子序列"a"只能算一次，"aa"也只能算一次。
我是在一个深夜刷题群里看到有人用AI工具（标题里提到的Qwen3.5-Plus）去解这道题的，AI很快给出了DP方程，但群里好几个人都说看不懂那个容斥减法的来源。于是我想把这个题彻底掰开揉碎讲一遍——不仅讲代码，更要把“为什么这个方程长这样”讲清楚。这篇文章适合刷题卡在Hard题上的朋友，也适合想系统理解区间DP和容斥去重的同学。
1. 题目解读：为什么这道Hard题值得专门写一篇
1.1 题意拆解：子序列、回文、去重三个词的组合拳
先逐个词拆开看难度。
第一个词是“子序列”。子序列不需要连续，这跟子串完全不同。比如s = "abcd"，子串里没有回文串，但子序列里"a"、"b"、"c"、"d"都是长度为1的回文子序列。这一下子就把枚举空间从O(n^2)的子串级别撑到了O(2^n)的子序列级别。
第二个词是“回文”。回文序列要求从左往右读和从右往左读一样。这导致我们必须关心区间两端字符的关系：如果两端相同，内部所有回文都可以被“包一层”形成新的回文；如果两端不同，两边的回文集合相对独立，需要合并去重。
第三个词才是真正的杀招——去重。我一开始想得比较简单：定义dp[i][j]为s[i]到s[j]区间内的回文子序列数量，然后想办法用子区间推大区间。但如果只是简单地把左右两边的数量相加，同一个回文子序列会被重复计算很多次。尤其像"abca"这种字符重复出现的串，不去重的话结果会膨胀得很厉害。题目加了一个"1e9+7取模"，本质上也是在告诉我们：这个数字会非常大，去重必须做彻底。
所以这道题考点很明确：区间DP打底，容斥原理去重，再配合取模运算的细节处理。任何一环做不对，答案都是错的。
1.2 难点定位：先搞清楚暴力解的死穴在哪
我刚开始尝试这道题的时候，脑子里冒出的第一个方案是暴力枚举所有子序列。s长度是1000，2的1000次方这个数字大到没有意义，肯定不行。
退一步，如果只统计回文子串，那么马拉车算法是O(n)的，因为子串有明确的“中心扩展”性质。但子序列不连续，中心扩展的套路直接失效。
再退一步，如果不去重，用dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]这个普通区间合并公式，是可以O(n^2)算出一个数量的，但那个数量是“所有回文子序列的个数”，不是“所有不同的回文子序列的个数”。区别在哪？比如s = "aaa"，不去重的公式会把"a"这个回文子序列算了3次（分别以三个位置的'a'结尾或开头）。题目要求的是不同内容，也就是只能算1次。
这个“内容去重”的要求，直接决定了转移方程不能只是简单加减，必须额外处理“相同字符在同一区间内重复出现”的情况。这也是为什么很多第一次做这道题的人会觉得答案差很多：不是数量算少了，而是重复的根本没去掉。
2. 思路推导：区间DP和容斥是怎么一步步凑齐的
2.1 为什么是区间DP：从“连续”到“不连续”的思维转换
处理字符串问题，一旦上来了区间DP，第一反应就是定义dp[i][j]代表子串s[i..j]的某种答案。对于730这道题，dp[i][j]就表示在s[i]到s[j]这个区间里，一共有多少个不同的非空回文子序列。
为什么区间DP是合适的？因为回文子序列有很好的“区间嵌套”性质：一个回文子序列从两端看，如果最外层字符相等，去掉两端之后内部依然是一个回文子序列；如果最外层字符不等，那么这个回文子序列要么只来自左半部分，要么只来自右半部分，要么来自更小的内部区间。
换句话说，大区间的回文子序列集合，可以由小区间的集合“生长”出来。这就是区间DP的典型特征。
但是这里有一个隐蔽的坑。普通的区间DP，比如石子合并、最长回文子串，合并时只需要关注区间端点，不需要关心区间内部的具体字符分布。而730不一样，去重逻辑要求我们快速知道区间内某个字符的“下一个位置”和“上一个位置”，否则无法判断会不会产生重复。
2.2 不等号第一刀：s[i] != s[j] 时的容斥方程
先看最简单的情况：s[i]不等于s[j]。
比如s = "abca"，只看区间[0,3]，两端'a'和'a'是相等的；那换一个区间比如[0,2]="abc"，两端'a'和'c'不相等。
当两端不等时，区间[i,j]内的所有回文子序列，要么来自s[i+1..j]，要么来自s[i..j-1]。这个可以理解成：讨论一个回文子序列的“来源”，它的最外层字符不可能是同时来自左端i和右端j（因为一旦同时取了s[i]和s[j]，这两个字符要使回文成立就必须相等，但这里不相等）。所以它或者不取s[i]，或者不取s[j]。
于是集合A = [i+1, j]内的回文子序列集合，集合B = [i, j-1]内的回文子序列集合。它们的并集就是[i,j]内的全部回文子序列。根据容斥原理：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
为什么要减掉dp[i+1][j-1]？因为A和B的交集恰好是既不用s[i]也不用s[j]的回文子序列，也就是完全落在区间[i+1, j-1]内的回文子序列。这个集合在A中有，在B中也有，被加了两次，所以必须减去一次。
这个公式很多刷过普通区间DP的人都见过，和求区间内不同子序列数量时用的方法一样。但它有个前提：两端不相等，所以不会产生“包裹两端形成新回文”的情况。
2.3 等号第二刀：s[i] == s[j] 时的包裹策略与三重分支
现在到了最核心、也最容易晕的部分：当s[i] == s[j]时，怎么推？
假设当前区间是[i, j]，且s[i] == s[j] == c。这时候，任何在[i+1, j-1]内的回文子序列，都可以在它的左右两侧各加上一个c，得到一个以c开头、c结尾的更大回文子序列。所以内部的所有回文子序列，数量是dp[i+1][j-1]的话，扩展之后数量还是dp[i+1][j-1]？不对，是每个内部回文子序列经过“包裹”都能产生一个新的回文子序列，所以这部分贡献是dp[i+1][j-1]份。
这时候又要考虑另一个来源：内部区间里本身就有一些以c开头或以c结尾的回文子序列。如果这些回文子序列再配合两端包裹，可能会产生重复。
具体来说，我需要在内部区间[i+1, j-1]里找到两件事：
- l = 从i+1往右找，第一个等于c的位置。
- r = 从j-1往左找，第一个等于c的位置。
然后分成三种情况推导。
第一种情况：内部完全找不到c，也就是[l, r]都不存在。
内部没有字符c，意味着dp[i+1][j-1]里所有回文子序列都不含c。包裹两端之后，产生的新回文子序列数量是dp[i+1][j-1]（每个内部回文被包一层）。同时，还有两个新的回文子序列是内部不可能提供的：单个字符"c"和双字符"cc"。这两个必须单独加进去。
所以dp[i][j] = 2 * dp[i+1][j-1] + 2。
有人可能会问，为什么单个字符"c"是新的？因为内部没有c，dp[i+1][j-1]里不可能包含"c"，而区间[i,j]现在多了两端两个c，所以"c"第一次出现。双字符"cc"也是同理。
第二种情况：内部恰好只有一个位置等于c，也就是l存在且l == r。
此时内部区间里有一个c。这个c本身可以形成单个字符回文"c"，所以dp[i+1][j-1]里已经包含了"c"。但是双字符"cc"（由内部这个c和某一端外部的c组成）是新的，内部很难产生“两个c相邻”的回文子序列，至少不是题目要统计的那种以s[i]和s[j]为两端扩展出来的"cc"。因此只需要加1个新回文子序列。
所以dp[i][j] = 2 * dp[i+1][j-1] + 1。
第三种情况：内部至少有两个位置等于c，也就是l < r。
这是最麻烦的情况。当l和r都存在且不相等时，内部区间就同时存在多个c。我们可以把内部的回文子序列分成两类：一类完全在[l+1, r-1]区间内，一类会经过l或者r位置上的c。
为什么这里会出现重复？因为s[l] = s[r] = c，这跟s[i]和s[j]一样。当我们把内部任意一个回文子序列用两端c包裹时，可能出现两种等价路径：一是以s[i]和s[j]作为外层包裹，二是以s[l]和s[r]作为外层包裹。如果内部回文子序列恰好夹在l和r之间，那么这两种包裹产生的最终回文子序列是相同的。
具体去重公式是：
dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]
解释起来就是：先把内部所有回文子序列都“包一层”，得到2 * dp[i+1][j-1]，但其中坐落在[l+1, r-1]范围内的回文子序列，包裹后会被重复计算两次，所以要减去一次dp[l+1][r-1]。
这个三角形的重复逻辑是这道题最抽象的地方。我自己第一次看到这个公式的时候，光靠看文字完全没法说服自己，后来是拿一个具体例子手动展开才彻底明白的。
2.4 边界处理与状态初始化
处理完三种情况，剩下的就是初始化。长度为1的区间，s[i..i]只有一个字符，它自身就是一个回文子序列，所以dp[i][i] = 1。
长度为2的区间不能单独特殊化，直接用上面的转移公式推就能得到正确结果。比如"ab"，两端不相等，dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] = 1 + 1 - 0 = 2，也就是"a"和"b"两个单字符回文。再比如"aa"，两端相等且内部空，按第一种情况，2 * 0 + 2 = 2，也就是"a"和"aa"，完全正确。
这里要注意一个细节：上面公式里的dp[i+1][j-1]在区间为空时要当作0处理，不能去访问一个不存在的下标。最稳妥的做法是单独初始化dp[i][i] = 1，然后长度从2开始循环，长度为2时内部区间是空的，直接代入空区间值为0。
还有一个容易踩的坑：我在讲解的时候用了l < r作为第三种情况的判断，但实际代码里更常见的是先判断l和r是否存在。很多解法是找到l和r之后分别赋初值，如果没找到就当成特殊值，然后统一处理。
3. 代码落地：一个干净可AC的Java实现
3.1 完整代码（带注释）
这道题我用Java写了一个比较清晰的版本，直接贴出来，后面逐步拆解。
class Solution { private static final int MOD = 1_000_000_007; public int countPalindromicSubsequences(String s) { int n = s.length(); char[] ch = s.toCharArray(); // 预处理每个位置右/左侧某个字符的最近位置 int[][] next = new int[n + 1][4]; int[][] prev = new int[n + 1][4]; for (int c = 0; c < 4; c++) { next[n][c] = n; prev[0][c] = -1; } for (int i = n - 1; i >= 0; i--) { for (int c = 0; c < 4; c++) { next[i][c] = next[i + 1][c]; } next[i][ch[i] - 'a'] = i; } for (int i = 1; i <= n; i++) { for (int c = 0; c < 4; c++) { prev[i][c] = prev[i - 1][c]; } if (i - 1 >= 0) { prev[i][ch[i - 1] - 'a'] = i - 1; } } long[][] dp = new long[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int len = 2; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (ch[i] != ch[j]) { dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % MOD; if (dp[i][j] < 0) { dp[i][j] += MOD; } } else { int left = next[i + 1][ch[i] - 'a']; int right = prev[j - 1][ch[i] - 'a']; if (left > right) { dp[i][j] = (2 * dp[i + 1][j - 1] + 2) % MOD; } else if (left == right) { dp[i][j] = (2 * dp[i + 1][j - 1] + 1) % MOD; } else { dp[i][j] = (2 * dp[i + 1][j - 1] - dp[left + 1][right - 1]) % MOD; if (dp[i][j] < 0) { dp[i][j] += MOD; } } } } } return (int) (dp[0][n - 1] % MOD); } }3.2 逐段拆解：pre数组的作用与为什么必须预处理
这段代码最需要注意的是next和prev的预处理。
题目明确说了输入字符串只包含'a'、'b'、'c'、'd'四种字符，所以数组第二维大小是4。但是真实刷题的时候，我建议写成26，万一面试官随手扩展一下字符集，代码还能复用。这里的next[i][c]表示从下标i开始向右看，第一个字符c出现的位置；如果不存在，存的是n，表示“越界”。
为什么必须预处理？因为区间DP的主循环是O(n^2)的，里面如果每次都要从i+1扫描到j-1找l和r，那就是O(n^3)，1000的长度会变成10亿次操作，直接超时。预处理的next和prev让每个区间找l和r的时间降到O(1)，整体才能稳定控制在O(n^2)。
然后看主循环。外层len是区间长度，内层i是区间左端点。为什么外层必须是长度？因为dp[i][j]依赖dp[i+1][j]（长度len-1）、dp[i][j-1]（长度len-1）、dp[i+1][j-1]（长度len-2）。也就是说，大区间依赖更小的区间，必须先算完所有长度为len-1和len-2的区间，再算长度为len的区间。如果像普通二维数组那样直接双重循环i、j，那么dp[i+1][j]可能还没被更新，得到的就是0，答案必然错误。
另外有一个细节：我用的dp是long类型。为什么要long？因为2 * dp[i+1][j-1]这个操作，在dp值接近MOD的时候，乘法可能超过int范围，直接用long可以避免溢出。最后返回的时候再强转成int，取模已经在过程中做过了。
3.3 复杂度分析：O(n^2)到底快在哪里
时间复杂度方面，预处理next和prev是O(4n)，DP主循环是O(n^2)，每组状态的计算都是O(1)，所以整体是O(n^2)。n = 1000时，状态数约50万个，这个量级对现代CPU来说非常轻松。
空间复杂度是O(n^2)，因为dp矩阵是n乘n。到这里可能会有人问，能不能像零一背包那样压缩成O(n)的滚动数组？答案是比较难的，原因是第三种情况的转移需要用到dp[left+1][right-1]，而这个left和right的位置与当前区间没有固定偏移关系，有的可能很远，有的可能很近，无法保证它刚好在某个“上一层”或“上两层”的位置。所以这道题的空间优化空间不大，老老实实开二维数组就好。
还有一个容易忽略的计算点：减法取模的负数处理。Java的%运算符在处理负数时结果是负数，比如-3 % 5 = -3，不是2。所以每次出现减法，我都在后面加了if (dp[i][j] < 0) dp[i][j] += MOD。还有一种做法是写成(value % MOD + MOD) % MOD，两行代码效果一样，但第一种在只减一次的情况下性能略好一点。
4. 调试实录：手推样例、常见坑与排查技巧
4.1 完整手推"bccb"：看状态表如何一步步填出来
等到代码写完之后有一个很关键的步骤：用一个测试样例去手推一遍，这样能验证自己对转移方程的理解是不是真的通了。我用s = "bccb"来走一遍，预期结果是6。
首先初始化所有dp[i][i] = 1，也就是所有单字符位置都只有1个回文子序列：
- dp[0][0] = 1，dp[1][1] = 1，dp[2][2] = 1，dp[3][3] = 1
然后长度为2的区间：
- dp[0][1]对应"bc"，两端不等：dp[1][1] + dp[0][0] - 空 = 1 + 1 - 0 = 2，对应"b"和"c"
- dp[1][2]对应"cc"，两端相等，内部为空：2 * 0 + 2 = 2，对应"c"和"cc"
- dp[2][3]对应"cb"，两端不等：1 + 1 - 0 = 2
长度为3的区间：
- dp[0][2]对应"bcc"，两端'b'和'c'不等：dp[1][2] + dp[0][1] - dp[1][1] = 2 + 2 - 1 = 3，这个3对应的回文子序列是"b"、"c"、"cc"
- dp[1][3]对应"ccb"，两端'c'和'b'不等：dp[2][3] + dp[1][2] - dp[2][2] = 2 + 2 - 1 = 3，对应"c"、"cc"、"b"
长度为4的区间：
- dp[0][3]对应"bccb"，两端都是'b'。内部区间是[1,2]="cc"。找left：从i+1=1开始向右第一个'b'，不存在，所以left = n或者比right大；找right：从j-1=2向左第一个'b'，也不存在。这种情况对应内部完全没有相同字符，2 * dp[1][2] + 2 = 2 * 2 + 2 = 6。
最终dp[0][3] = 6，跟预期完全一致。手动推一遍之后，我对那个“+2”的来源就特别有体感了：新增的2就是"b"和"bb"。很符合直觉，因为内部"cc"只有{ "c", "cc" }两个回文子序列，包上两个b得到"bcb"和"bccb"，再加上"b"和"bb"，一共6个。
4.2 高频踩坑点：负数取模、遍历方向、边界定位
第一个高频坑是负数取模。很多人在代码里用了减法之后忘记处理负数，结果得出的答案莫名其妙是负数或者错值。记住Java的%是保留符号的，凡是出现减法的地方都要额外做一次“加MOD再取模”的保护。最保险的做法是抽一个私有方法safeMod(long x)，内部统一处理，这样主逻辑清爽很多。
第二个高频坑是遍历方向。我见过很多人把代码写成：
for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { ... } }这种写法在计算dp[i][j]时用到的dp[i+1][j]和dp[i][j-1]都还没算出来，因为i+1比i大，而外层循环还没走到。必须按区间长度从小到大枚举，或者从尾部向头部枚举，总之要保证计算大区间之前所有依赖的小区间都已经就绪。
第三个高频坑是找left和right时的边界。left应该在(i+1, j-1)这个开区间内找，right同理。很多人写的时候直接把范围写成了(i, j)，结果把端点本身的字符也算进去了，导致判断条件永远命中“内部有字符”的情况，加的次数就错了。像上面代码里，我用的是next[i+1]和prev[j-1]，保证不会把两端字符算进去，这是一个很容易写错但代码上又不太显眼的细节。
还有一个我平时自己刷题时会踩的隐蔽坑：left和right的初始化值。如果没有找到字符，我习惯把left初始化为j，把right初始化为i，这样left > right就能直接落入第一种情况。用边界值的好处是避免引入额外的boolean标记，代码更短。但前提是你必须清楚left > right代表“没有内部相同字符”，如果搞成left >= right，就会把恰好只有单个相同字符的情况错误处理成“没有相同字符”，从而多加一个数量。
4.3 用AI工具辅助解这类DP的正确姿势
标题里出现了Qwen3.5-Plus，我猜不少人现在喜欢直接用AI工具来做这类Hard题。AI工具对这类经典题目的价值确实很大，但用的时候要有正确姿势。
我的经验是：不要直接复制AI给的代码交上去，而是把它当作一个“对标参考”。先让AI给出完整的转移方程推导，然后自己独立写一遍代码，再拿AI的代码来对照，重点看三个地方——减法容斥的处理方式、区间遍历的顺序、left和right的边界设置。
如果AI给的代码在本地跑样例能过，但你自己又说不清楚为什么能过，那这道题等于白刷。我建议每写完一个DP题都做两件事：第一，手动推一个小样例的状态表，比如上面的"bccb"；第二，构造一个暴力解（DFS枚举所有子序列去重），然后在随机小字符串上对拍，验证DP结果和暴力结果完全一致。对拍是验证DP正确性最可靠的手段，没有之一。
顺带说一句，AI在解这类题时也会犯边界错误，尤其是left和right的初始值设置。我用AI工具做过几次测试，它写的代码有时候在"abca"这种字符出现两次但不在内部重叠的例子上会错得悄无声息。所以千万别把AI当成免检答案，只能当成一个“会说话的草稿纸”。
5. 扩展与思考：一道题背后的算法地图
5.1 从子序列到子串：问题变形之后的工具切换
LeetCode 730研究的是子序列。如果把问题改成“统计字符串中不同的回文子串数量”，那就完全是另一套解法了，最有名的是马拉车（Manacher）算法，O(n)时间内求出所有回文半径，再用半径信息计算不同回文子串数量。
为什么这两个问题用的工具完全不同？因为子串要求连续，连续结构带有强烈的“中心扩展”性质，一个回文子串的内部一定是连续对称的；而子序列允许跳着取，这种“跳跃性”破坏了中心扩展的前提，却适合区间DP的嵌套结构。
我在实际做题的时候最受益的一个思维方式是：先判断题目给的是连续还是非连续结构，再判断需要去重还是不需要去重，这两个维度直接决定了是用马拉车、后缀数组、还是区间DP。拿730来说，“非连续”加上“需要去重”，区间DP几乎是唯一的主流方案。
5.2 如果n变大，空间还能压缩吗
有时候刷题会自然想到，如果n变成2000甚至5000，这个O(n^2)的深度和内存还能撑住吗？
先说时间复杂度。5000的O(n^2)是2500万状态，每一个状态是O(1)的运算，在Java里大概几百毫秒，是可以吃的。但空间复杂度就有点悬了，5000乘以5000的long二维数组是25M个long，大概200MB内存，大概率超限。
所以确实有人尝试用滚动数组优化空间。但前面提过，这个问题跟普通背包DP不同处在于，状态转移里面有一项dp[left+1][right-1]，它的left和right是当前位置i、j处的字符在区间内部的下一个和上一个出现位置，这个区间长度可能跨很多层，并不是简单的“上一行”或者“上两行”，滚动数组很难覆盖到所有历史层。
一种变通思路是分治或者用更复杂的数据结构，但实际刷题场景中，题目把n限制在1000，其实就是在暗示我们用O(n^2)的二维DP，不用强行优化。
5.3 这类“可重复字符+去重计数”DP的通用套路
复盘完整道题，我觉得有一个通用套路非常值得记录：当题目要求统计“不同的”某种结构时，要在转移方程里专门为“重复字符”建立结构性的去重项。
以730为例，普通区间合并公式dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]只能解决两端字符不等的情况。一旦两端字符相等，所有内部回文都能被“包裹扩展”，而重复恰恰发生在多个相同字符把整个区间分割成更小的对称结构时。这时候去重项的dp[left+1][right-1]本质上是在减去那些“被两端和内部同色字符同时包裹”的结构。
类似的结构还可以在统计本质不同子序列数量的题目里看到，只不过那边用的是字符上一次出现位置去重。可以说，凡是“不同”二字出现，脑子里就要立刻拉起警报：找重复模式，然后确定容斥项。
把这道题彻底吃透之后，我之前看很多区间DP题都有豁然开朗的感觉。后来我又回头用对拍脚本测了十几个随机字符串，发现DP和暴力结果全部一致，这才真正放心。个人刷题的习惯也更清晰了：第一遍理解不了转移方程就先抄一遍跑通，然后挑个小样例手推，最后再用暴力解对拍。至于AI工具生成的那些“标准答案”，我把它们当成同事给的评审意见，不会再盲目信任一整段代码。这一步看起来简单，但对DP这类“一错就全错”的题目来说，是最省时间的护身符。
