LeetCode 730详解：区间DP与容斥原理解决不同回文子序列计数-北京尧图网络

第一次看到LeetCode 730这道题的时候我的第一反应是“这题怎么又是Hard”。再仔细读两遍发现它把三个很容易让人头大的点揉在了一起子序列、回文、去重。单独看每个词都没那么可怕但是组合起来就成了经典的区间DP难题。题目给一个字符串s要求返回所有不同的非空回文子序列的数量结果对1e97取模。所谓“不同”指的是内容不同比如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这种字符重复出现的串不去重的话结果会膨胀得很厉害。题目加了一个1e97取模本质上也是在告诉我们这个数字会非常大去重必须做彻底。所以这道题考点很明确区间DP打底容斥原理去重再配合取模运算的细节处理。任何一环做不对答案都是错的。1.2 难点定位先搞清楚暴力解的死穴在哪我刚开始尝试这道题的时候脑子里冒出的第一个方案是暴力枚举所有子序列。s长度是10002的1000次方这个数字大到没有意义肯定不行。退一步如果只统计回文子串那么马拉车算法是O(n)的因为子串有明确的“中心扩展”性质。但子序列不连续中心扩展的套路直接失效。再退一步如果不去重用dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][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[i1..j]要么来自s[i..j-1]。这个可以理解成讨论一个回文子序列的“来源”它的最外层字符不可能是同时来自左端i和右端j因为一旦同时取了s[i]和s[j]这两个字符要使回文成立就必须相等但这里不相等。所以它或者不取s[i]或者不取s[j]。于是集合A [i1, j]内的回文子序列集合集合B [i, j-1]内的回文子序列集合。它们的并集就是[i,j]内的全部回文子序列。根据容斥原理dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1]为什么要减掉dp[i1][j-1]因为A和B的交集恰好是既不用s[i]也不用s[j]的回文子序列也就是完全落在区间[i1, j-1]内的回文子序列。这个集合在A中有在B中也有被加了两次所以必须减去一次。这个公式很多刷过普通区间DP的人都见过和求区间内不同子序列数量时用的方法一样。但它有个前提两端不相等所以不会产生“包裹两端形成新回文”的情况。2.3 等号第二刀s[i] s[j] 时的包裹策略与三重分支现在到了最核心、也最容易晕的部分当s[i] s[j]时怎么推假设当前区间是[i, j]且s[i] s[j] c。这时候任何在[i1, j-1]内的回文子序列都可以在它的左右两侧各加上一个c得到一个以c开头、c结尾的更大回文子序列。所以内部的所有回文子序列数量是dp[i1][j-1]的话扩展之后数量还是dp[i1][j-1]不对是每个内部回文子序列经过“包裹”都能产生一个新的回文子序列所以这部分贡献是dp[i1][j-1]份。这时候又要考虑另一个来源内部区间里本身就有一些以c开头或以c结尾的回文子序列。如果这些回文子序列再配合两端包裹可能会产生重复。具体来说我需要在内部区间[i1, j-1]里找到两件事l 从i1往右找第一个等于c的位置。r 从j-1往左找第一个等于c的位置。然后分成三种情况推导。第一种情况内部完全找不到c也就是[l, r]都不存在。内部没有字符c意味着dp[i1][j-1]里所有回文子序列都不含c。包裹两端之后产生的新回文子序列数量是dp[i1][j-1]每个内部回文被包一层。同时还有两个新的回文子序列是内部不可能提供的单个字符c和双字符cc。这两个必须单独加进去。所以dp[i][j] 2 * dp[i1][j-1] 2。有人可能会问为什么单个字符c是新的因为内部没有cdp[i1][j-1]里不可能包含c而区间[i,j]现在多了两端两个c所以c第一次出现。双字符cc也是同理。第二种情况内部恰好只有一个位置等于c也就是l存在且l r。此时内部区间里有一个c。这个c本身可以形成单个字符回文c所以dp[i1][j-1]里已经包含了c。但是双字符cc由内部这个c和某一端外部的c组成是新的内部很难产生“两个c相邻”的回文子序列至少不是题目要统计的那种以s[i]和s[j]为两端扩展出来的cc。因此只需要加1个新回文子序列。所以dp[i][j] 2 * dp[i1][j-1] 1。第三种情况内部至少有两个位置等于c也就是l r。这是最麻烦的情况。当l和r都存在且不相等时内部区间就同时存在多个c。我们可以把内部的回文子序列分成两类一类完全在[l1, 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[i1][j-1] - dp[l1][r-1]解释起来就是先把内部所有回文子序列都“包一层”得到2 * dp[i1][j-1]但其中坐落在[l1, r-1]范围内的回文子序列包裹后会被重复计算两次所以要减去一次dp[l1][r-1]。这个三角形的重复逻辑是这道题最抽象的地方。我自己第一次看到这个公式的时候光靠看文字完全没法说服自己后来是拿一个具体例子手动展开才彻底明白的。2.4 边界处理与状态初始化处理完三种情况剩下的就是初始化。长度为1的区间s[i..i]只有一个字符它自身就是一个回文子序列所以dp[i][i] 1。长度为2的区间不能单独特殊化直接用上面的转移公式推就能得到正确结果。比如ab两端不相等dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1] 1 1 - 0 2也就是a和b两个单字符回文。再比如aa两端相等且内部空按第一种情况2 * 0 2 2也就是a和aa完全正确。这里要注意一个细节上面公式里的dp[i1][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)的里面如果每次都要从i1扫描到j-1找l和r那就是O(n^3)1000的长度会变成10亿次操作直接超时。预处理的next和prev让每个区间找l和r的时间降到O(1)整体才能稳定控制在O(n^2)。然后看主循环。外层len是区间长度内层i是区间左端点。为什么外层必须是长度因为dp[i][j]依赖dp[i1][j]长度len-1、dp[i][j-1]长度len-1、dp[i1][j-1]长度len-2。也就是说大区间依赖更小的区间必须先算完所有长度为len-1和len-2的区间再算长度为len的区间。如果像普通二维数组那样直接双重循环i、j那么dp[i1][j]可能还没被更新得到的就是0答案必然错误。另外有一个细节我用的dp是long类型。为什么要long因为2 * dp[i1][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[left1][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] 1dp[1][1] 1dp[2][2] 1dp[3][3] 1然后长度为2的区间dp[0][1]对应bc两端不等dp[1][1] dp[0][0] - 空 1 1 - 0 2对应b和cdp[1][2]对应cc两端相等内部为空2 * 0 2 2对应c和ccdp[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、ccdp[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从i11开始向右第一个b不存在所以left n或者比right大找right从j-12向左第一个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[i1][j]和dp[i][j-1]都还没算出来因为i1比i大而外层循环还没走到。必须按区间长度从小到大枚举或者从尾部向头部枚举总之要保证计算大区间之前所有依赖的小区间都已经就绪。第三个高频坑是找left和right时的边界。left应该在(i1, j-1)这个开区间内找right同理。很多人写的时候直接把范围写成了(i, j)结果把端点本身的字符也算进去了导致判断条件永远命中“内部有字符”的情况加的次数就错了。像上面代码里我用的是next[i1]和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[left1][right-1]它的left和right是当前位置i、j处的字符在区间内部的下一个和上一个出现位置这个区间长度可能跨很多层并不是简单的“上一行”或者“上两行”滚动数组很难覆盖到所有历史层。一种变通思路是分治或者用更复杂的数据结构但实际刷题场景中题目把n限制在1000其实就是在暗示我们用O(n^2)的二维DP不用强行优化。5.3 这类“可重复字符去重计数”DP的通用套路复盘完整道题我觉得有一个通用套路非常值得记录当题目要求统计“不同的”某种结构时要在转移方程里专门为“重复字符”建立结构性的去重项。以730为例普通区间合并公式dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1]只能解决两端字符不等的情况。一旦两端字符相等所有内部回文都能被“包裹扩展”而重复恰恰发生在多个相同字符把整个区间分割成更小的对称结构时。这时候去重项的dp[left1][right-1]本质上是在减去那些“被两端和内部同色字符同时包裹”的结构。类似的结构还可以在统计本质不同子序列数量的题目里看到只不过那边用的是字符上一次出现位置去重。可以说凡是“不同”二字出现脑子里就要立刻拉起警报找重复模式然后确定容斥项。把这道题彻底吃透之后我之前看很多区间DP题都有豁然开朗的感觉。后来我又回头用对拍脚本测了十几个随机字符串发现DP和暴力结果全部一致这才真正放心。个人刷题的习惯也更清晰了第一遍理解不了转移方程就先抄一遍跑通然后挑个小样例手推最后再用暴力解对拍。至于AI工具生成的那些“标准答案”我把它们当成同事给的评审意见不会再盲目信任一整段代码。这一步看起来简单但对DP这类“一错就全错”的题目来说是最省时间的护身符。

LeetCode 730详解：区间DP与容斥原理解决不同回文子序列计数

相关推荐

AI透明度危机：大模型安全评测、脑机接口与幻觉治理的底层逻辑

LeetCode 730 不同回文子序列：动态规划去重与Java实现

数据库设计与应用开发实战：ER图、索引优化与事务控制要点

更多资讯

Tekla图纸二次开发入门：零基础实现自动出图与图框定制

把AI预言变成可执行的小实验：未来十年的认知框架

基于SE-ResNet的C-MAPSS航空发动机剩余寿命预测Matlab实现

Nano Banana 2登顶实测：Gemini 3.1 Flash Image多轮编辑与文字渲染深度评测

8位单片机汇编例程实战：从LED闪烁到定时器中断

多元积分复习笔记：从二重三重到曲线曲面的“正元”体系

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？