LeetCode 730 不同回文子序列：动态规划去重与Java实现-北京尧图网络

LeetCode 730 这题光看标题就带着一股 hard 题特有的气场countPalindromicSubsequences统计不同回文子序列。我第一次刷到的时候先让 Qwen3.5-Plus 帮忙给了一版思路模型不到十秒就甩出了“二维 DP 容斥”的大方向但等我真正把public int countPalindromicSubsequences(String s)这层皮剥开、手推了几个样例之后才发现公式谁都能背真正会写的人不多。这道题很适合拿来检验你对动态规划的理解深度它不考什么高深的算法考的是“去重”这件事在状态设计里怎么落地。子序列可以跳着选、回文又要首尾匹配、统计的又是“内容不同”而不是“位置组合不同”这三个条件叠在一起常规回文 DP 的直觉会全部失效。这篇文章我会从题目本身的坑讲起把状态怎么设、转移为什么要分成三种情况、dp[l1][r-1]到底在减什么、Java 代码怎么写不踩负数取模全部拆开讲清楚。不管你是在准备面试还是被这题虐过想彻底搞懂应该都能拿走一点东西。1. 先把题目看明白统计的是内容不是位置1.1 子序列到底怎么数先对齐一下基础概念。回文子序列里的“子序列”不要求字符连续只要求相对顺序不变。拿题目自带的例子s bccb来说bb这个回文子序列就取的是第 0 个字符和第 3 个字符中间隔着cc但完全合法。题目要统计的是所有“不同的非空回文子序列”的数量然后对10^9 7取模。注意“不同”这个词比较的是子序列的字符串内容不是它由哪些下标组成。这个区别是整道题的核心陷阱。举个最简单的极端例子s aaaa按位置组合数的话长度为 2 的aa有好多组取法但按内容去重之后整个字符串的不同回文子序列只有四种a、aa、aaa、aaaa。所以这道题不能靠枚举子序列位置来算。如果字符串长度到 10002^n种子序列直接会让任何暴力方案当场去世。看到“计数去重取模”三个关键词基本就能确定思路要往动态规划上走。1.2 为什么不能直接套常规回文 DP写过最长回文子序列的同学应该对这类状态很熟dp[i][j]表示s[i..j]区间内的某个最优值转移的时候看两端字符是否相等。但 LCS 式的回文 DP 求的是“最长长度”长度的重复不影响最优值而 730 求的是“个数”一旦同一个回文内容能从不同位置组合里冒出来简单加法的计数就会失控。比如有人会凭感觉写出这样的转移如果s[i] s[j]那么dp[i][j] dp[i1][j-1] * 2 2。这个公式只在一种前提条件下成立中间区间里没有任何一个字符等于s[i]。可如果中间也有相同的字符这个* 2 2就会把很多回文重复计算。拿s aaaaa手推一下就会发现必须区分中间到底有几个相同的字符分别给不同的公式。这就是这题与普通回文 DP 最本质的差异它要求你额外掌握“内部相同字符的分布信息”。2. 状态与边界dp[i][j] 里藏着最容易错的两个约定2.1 两种主流思路对比LeetCode 730 的题解区里能搜到两种主流方案。第一种是三维 DPdp[k][i][j]表示区间[i, j]内、以字符k开头并且以字符k结尾的不同回文子序列个数。字符集只有 4 个题目保证只含a、b、c、d所以空间大概是4 * n^2。这种方案的好处是思路很直接每个维度对应一个约束不太好漏状态坏处是转移分支也不少代码写起来比较长而且三维数组的索引比较容易把自己绕晕。第二种是二维 DPdp[i][j]直接表示区间[i, j]内所有不同回文子序列的数量。转移公式很精炼但中间藏着“内部相同字符最左、最右位置”的预处理公式还分三种情况尤其是第三种情况里的减法非常反直觉。我最后选择了这种方案因为它的最终代码更短、可优化空间更大而且面试手写时也更容易讲清楚。代价就是你必须把三个公式的来源彻底弄明白不能死记。2.2 我为什么选二维 DP 预处理位置二维 DP 的转移需要回答一个问题当s[i] s[j]时内部区间[i1, j-1]里到底有几个字符等于这个s[i]这个问题可以用笨办法在每次转移时用一个while循环从i1扫到j-1当场找最左和最右的相同字符。但这样每个状态都可能要扫 O(n) 的长度整体复杂度会变成 O(n^3)。字符串长度到 1000 的时候10^9量级的操作在 LeetCode 上基本是超时边缘。所以需要预处理两个数组next[i][c]从下标i开始向右看字符c第一次出现的位置prev[i][c]从下标i开始向左看字符c第一次出现的位置。建表方法很简单next从右往左填prev从左往右填。有了这两个表转移时查next[i1][s[i]-a]和prev[j-1][s[i]-a]都是 O(1) 操作总复杂度就能稳在 O(n^2)。2.3 边界初始化空区间到底算不算一个回文这里必须约法三章否则后面所有公式都会出问题。我的约定是dp[i][j]只统计非空回文子序列的个数空串不算数。当i j时区间里只有一个字符它本身就是一个长度为 1 的回文所以dp[i][i] 1当i j时区间不存在视为 0数组默认值刚好就是 0长度为 2 的区间dp[i][i1]会用到空区间dp[i1][i]此时直接按 0 参与运算。也有题解把空串算进dp里最后答案再减 1。两种约定都能写出正确代码但建议不要混用。你在网上看到某个公式里的 2或 1如果对不上先检查对方是不是把空串算进去了。3. 转移方程逐行拆解最难的是那个减法3.1 两端字符不同这里只是普通的集合容斥如果s[i] ! s[j]两端字符没法参与构成跨越整个区间的回文所以答案其实就来自两个子区间[i1, j]和[i, j-1]。但这两个子区间的并集会重复覆盖[i1, j-1]于是公式变成了dp[i][j] dp[i1][j] dp[i][j-1] - dp[i1][j-1]这就像求两个集合的并集大小左边部分加右边部分再减去中间重叠的部分。这段逻辑本身不难但初学者最容易忘的是减法结果可能是负数尤其是在取模环境下。Java 的%运算对负数返回负数所以代码里要写成(dp[i1][j] dp[i][j-1] - dp[i1][j-1] MOD) % MOD先补一个模数再取模。3.2 两端相同但中间没有相同字符2 倍加 2现在进入重头戏。设c s[i] s[j]记内部区间[i1, j-1]的不同回文子序列数量为m dp[i1][j-1]。如果内部区间里一个c都没有那么新增的回文可以分为四类内部原来就有的回文共m个把内部每个回文x两边各包一个c得到c x c共m个单字符回文c本身之前内部没有新增 1 个双字符回文cc由两个端点直接组成新增 1 个。所以总数就是dp[i][j] 2 * dp[i1][j-1] 2拿s aa验证内部为空m 0结果2 * 0 2 2对应a和aa正确。再拿s aba验证内部只有一个bm 1结果2 * 1 2 4对应a、b、aa、aba也正确。3.3 中间恰好一个相同字符2 倍加 1如果内部区间里恰好有一个c情况就不一样了。上一节第 3 类说的单字符c已经在内部出现过了内部区间本身至少要贡献一个c这个回文子序列所以c不再是新增项。但双字符cc仍然是新的因为之前只有单个c没有两个c同时出现。于是公式变成dp[i][j] 2 * dp[i1][j-1] 1拿s aaba验证一下。区间[0, 3]两端是a内部[1, 2]是ab里面有一个a下标 1所以符合“恰好一个”。先算dp[1][2]区间ab的两端字符不同dp[1][2] dp[2][2] dp[1][1] - 0 2。再代公式2 * 2 1 5。手动枚举所有不同回文子序列a、b、aa、aaa、aba正好 5 个。这里如果错用成 2结果会多出来一个不存在的回文小样例一跑就能暴露。3.4 中间至少两个相同字符为什么要减 dp[l1][r-1]这是全题最反直觉的地方。如果内部区间里有至少两个c前面那种2m1的加法就不成立了。因为内部已经存在大量以c开头、以c结尾的回文当你再在外面包一层c时会产生不少内容和内部原有回文重复的东西。简单加法的“新增”部分没法继续精确分出来。正确的公式变成了dp[i][j] 2 * dp[i1][j-1] - dp[l1][r-1]其中l和r分别是内部区间里从左往右看第一个等于c的位置和从右往左看第一个等于c的位置。用s aaaaa来验证这个例子最能说明问题。区间[0, 4]两端是a内部[1, 3]是aaa里面最左的a是下标 1最右的a是下标 3所以l 1、r 3。先算dp[1][3]区间aaa两端相同内部恰好一个a所以dp[1][3] 2 * dp[2][2] 1 2 * 1 1 3。再代当前公式dp[0][4] 2 * dp[1][3] - dp[2][2] 2 * 3 - 1 5手动枚举aaaaa的不同回文子序列a、aa、aaa、aaaa、aaaaa确实就是 5 个。如果不减后面那一项会算出 6 个多出来的那个就是被重复计数的回文。为什么偏偏减的是dp[l1][r-1]而不是别的区间直观理解是内部那些“以c开头并且以c结尾”的回文在包外层c之后会和另一种计数路径重叠。而这些重叠回文去掉最外层c之后剩下的部分正好落在[l1, r-1]区间内。也就是说[l1, r-1]的全部回文数量恰好就是重复计数的总量。所以公式里减去的不是内部全部回文数而是“内部最左和最右相同字符夹出来的那一小块”的回文数。这地方很容易记错我的经验是先用s aaaaa和s bccb两个样例把三种分支都跑一遍公式自然就记住了纯背的话第二天准忘。4. Java 实现从伪代码到可以提交的代码4.1 预处理每个位置之后和之前的最近字符我建议把next和prev都开成int[n 1][4]多出来的第n行用来放哨兵值。next的构建逻辑是从右往左复制int[][] next new int[n 1][4]; for (int c 0; c 4; c) { next[n][c] n; // 哨兵表示没找到 } for (int i n - 1; i 0; i--) { for (int c 0; c 4; c) { next[i][c] next[i 1][c]; } next[i][s.charAt(i) - a] i; }prev的构建逻辑是从左往右复制int[][] prev new int[n][4]; for (int c 0; c 4; c) { prev[0][c] -1; // 哨兵表示没找到 } prev[0][s.charAt(0) - a] 0; for (int i 1; i n; i) { for (int c 0; c 4; c) { prev[i][c] prev[i - 1][c]; } prev[i][s.charAt(i) - a] i; }这里有两个哨兵细节next[n]全填n表示从下标n开始向右什么也找不到prev[0]在设置自己之前全填-1表示从下标 0 向左什么也找不到。这些哨兵在判断“内部区间没有相同字符”时会发挥关键作用。4.2 完整代码与注释完整的 Java 实现如下public int countPalindromicSubsequences(String s) { final int MOD 1_000_000_007; int n s.length(); if (n 0) { return 0; } int[][] next new int[n 1][4]; for (int c 0; c 4; c) { next[n][c] n; } for (int i n - 1; i 0; i--) { for (int c 0; c 4; c) { next[i][c] next[i 1][c]; } next[i][s.charAt(i) - a] i; } int[][] prev new int[n][4]; for (int c 0; c 4; c) { prev[0][c] -1; } prev[0][s.charAt(0) - a] 0; for (int i 1; i n; i) { for (int c 0; c 4; c) { prev[i][c] prev[i - 1][c]; } prev[i][s.charAt(i) - a] i; } long[][] dp new long[n][n]; for (int len 1; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (len 1) { dp[i][j] 1; continue; } if (s.charAt(i) ! s.charAt(j)) { dp[i][j] (dp[i 1][j] dp[i][j - 1] - dp[i 1][j - 1] MOD) % MOD; } else { int c s.charAt(i) - a; int l next[i 1][c]; int r prev[j - 1][c]; if (l r) { // 中间没有相同字符 dp[i][j] (2 * dp[i 1][j - 1] 2) % MOD; } else if (l r) { // 中间恰好一个相同字符 dp[i][j] (2 * dp[i 1][j - 1] 1) % MOD; } else { // 中间至少两个相同字符需要容斥 dp[i][j] (2 * dp[i 1][j - 1] % MOD - dp[l 1][r - 1] MOD) % MOD; } } } } return (int) (dp[0][n - 1] % MOD); }这段代码有几个地方需要特别说明。dp数组我用了long而不是int。虽然每次结果都取模了但在2 * dp[i 1][j - 1] 2这一步如果dp是int两个MOD量级的数相加再乘 2 就可能溢出。用long可以彻底避开这个风险最后返回时再强转回int。减法操作我全部写成(a - b MOD) % MOD。这是 Java 取模的老坑(-1) % MOD在数学上应该是MOD - 1但 Java 会返回-1。所以只要有减法就必须先补一个MOD再取模。l r这个判断同时覆盖了一种边界情况当区间长度为 2 时next[i1][c]和prev[j-1][c]可能查出来的是两个端点位置但i1和j-1之间是空的此时l一定大于r所以会走进“中间没有相同字符”的分支结果正好是2。这也是能用哨兵值省掉一堆if判断的原因。4.3 复杂度与取模细节时间复杂度是 O(n^2)因为区间个数是n * (n 1) / 2每个区间的转移都是常数操作。空间复杂度同样是 O(n^2)dp数组占大头。字符只有 4 个next和prev各占4n的空间几乎可以忽略不计。如果面试官追问能不能优化空间你可以说理论上能通过滚动数组省掉一维但这道题的转移会跳到任意更短的区间[l1, r-1]不是简单的相邻层依赖滚动之后实现复杂度会明显上升。LeetCode 的n范围下一般不超过 1000开一个1000x1000的long数组大约 8MB完全够用没必要为了省空间牺牲代码可读性。5. 实测、避坑与用大模型辅助的一点体会5.1 我踩过的三个坑第一个坑是初始化。dp[i][i] 1这行看着不起眼但漏掉之后整个 DP 表会从底层开始错。因为数组默认值是 0单字符区间会被当成 0 个回文后面所有区间全部归零。我建议写完代码先跑一个s a的最小用例如果返回 0第一步就能检查出来。第二个坑是“恰好一个相同字符”时用了 2。这个错误特别隐蔽因为s aba这类样例下 2和 1的结果都是 4不对s aba中间没有相同字符走的是另一个分支。真正能测出这个错误的是s aaba正确结果是 5用 2会得到 6。所以小样例一定要选对别拿一个只能覆盖部分分支的用例测完就觉得稳了。第三个坑是负数取模。dp[i1][j] dp[i][j-1] - dp[i1][j-1]在数学上一定是非负的但因为中间过程取模最后的数值可能是负的。我第一次写的时候直接返回(int) (dp[0][n-1] % MOD)结果在几个样例上看到负数排查了半天才意识到是 MOD的问题。5.2 常见问题速查表症状可能原因处理方法返回负数Java 取模对负数不友好所有减法写成(a - b MOD) % MOD单个字符返回 0忘记初始化dp[i][i] 1长度 1 的区间单独赋值aaba结果多 1恰好一个相同字符时错用 2改为 1[aaaaa]结果多 1两个及以上相同字符时忘了容斥减去dp[l1][r-1]大数据超时转移时用循环找内部相同字符预处理next和prev数组5.3 用 Qwen3.5-Plus 辅助解题的观察说回标题里的 Qwen3.5-Plus。我的使用方式是把题目原文和public int countPalindromicSubsequences(String s)这个方法签名一起贴给模型让它先给一版思路和代码。模型确实能在很短时间内给出“二维 DP 三个分支”的正确框架甚至转移式也基本写对了但在2、1、-dp[l1][r-1]这几个细节上第一版代码里的边界处理是有问题的。这不是模型能力不行而是这类题的边界条件本身就依赖对语义的精确理解语言模型容易把“见过的公式”直接吐出来但很难替你验证公式在边界条件下是否成立。我的建议是用模型生成的代码当参考但提交之前一定自己动手把aa、aba、aaba、aaaaa、bccb这几个样例跑一遍。只要你手推能把这五个串的结果全部对上代码基本就不会错了。另外还有一个实用技巧让模型解释每一条转移公式时要求它“不要讲抽象概念直接对着bccb把 dp 表填一遍”。让模型做一次具体的表格推导通常能暴露出更多隐藏的错误理解。这个思路对所有类似的 hard 题都适用。5.4 我个人实际操作中的体会这题刷完之后我最强烈的感受是动态规划的边界条件不是背出来的是拿小样例逼出来的。2、1、-dp[l1][r-1]这三个分支光看公式很容易混淆但只要你在草稿纸上把aaaaa的集合慢慢拆一遍就会理解dp[l1][r-1]到底在减去哪部分重复。以后遇到任何“回文计数去重”的变体题第一步先想清楚哪些回文会被重复构造第二步再去找重复部分对应的子区间基本就能稳住了。如果后面还想继续深挖可以试试把字符集从 4 扩展到 26或者把next/prev数组换成“每个字符的位置列表二分查找”的写法。面试时能讲清楚从 O(n^3) 暴力到 O(n^2) 预处理的优化过程会比单纯背下这道题的答案更有说服力。

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

相关推荐

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

DE/SHADE/L-SHADE算法在CEC2005基准函数上的Matlab对比实验及实现细节

AI论文写作工具横评：9款工具全流程实测与避坑指南

更多资讯

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 成本测算与选型避坑（附配置）

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