示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读本文围绕《剑指 Offer专项突击版》第 097 题「子序列的数目」numDistinct展开从暴力递归的困境出发逐步推导出二维动态规划的状态定义与转移方程再进一步给出空间压缩到 O(n) 的一维滚动数组写法。读完本文你将掌握这类计数型字符串子序列 DP的完整建模套路、多语言实现要点以及理解为什么一维优化必须倒序更新这一经典考点并能在 lcof2/剑指 Offer II 097. 子序列的数目/README.md 与仓库源码之间快速对照学习。题目理解与问题建模子序列的定义题目给定两个字符串s和t要求计算在s的子序列中t出现的个数。字符串的子序列是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如ACE是ABCDE的一个子序列删除B、D即可而AEC不是因为删除字符后E无法出现在C之前。注意这里的出现个数统计的是选取方案数而不是简单的位置数同一个目标串可能由多组不同的下标组合构成每一组下标都算一种方案。输入输出示例示例 1输入s rabbbit, t rabbit 输出3 解释有 3 种从 s 中选取下标得到 rabbit 的方案 rabbbit rab bbit rabb bit对应下标组合分别为ra b b it、ra b bbit、rab b bit本质上就是s中三处b与t中两个b的不同配对方式。示例 2输入s babgbag, t bag 输出5数据约束与答案范围0 s.length, t.length 1000s和t由英文字母组成题目数据保证答案符合 32 位带符号整数范围由于长度上限达到 1000枚举所有下标组合的指数级做法完全不可行必须使用动态规划。本题与 LeetCode 主站 115. 不同的子序列 完全相同属于经典的困难难度字符串 DP 题在仓库 lcof2/README.md 中标注的标签为字符串、动态规划。方法一二维动态规划为什么朴素递归不可行如果按位置递归选或不选s中的字符去匹配t在无记忆化的情况下大量后缀对(s[i:], t[j:])会被重复计算。s与t长度均可达 1000递归树规模指数爆炸因此必须把重叠子问题缓存下来——这正是动态规划的切入点。状态定义定义f[i][j]表示字符串s的前i个字符中子序列构成字符串t的前j个字符的方案数。这里i从 0 到mm s.lengthj从 0 到nn t.length。最终答案就是f[m][n]。状态转移方程的推导当i 0时考虑s的第i个字符s[i-1]是否参与匹配t的第j个字符t[j-1]当s[i-1] ! t[j-1]时末尾字符不相同s[i-1]无法作为t[j-1]的匹配来源只能选择不取它方案数直接继承s前i-1个字符的状态即f[i][j] f[i-1][j]当s[i-1] t[j-1]时末尾字符相同有两种选择不取s[i-1]方案数为f[i-1][j]取s[i-1]去匹配t[j-1]此时s前i-1个字符需要构成t前j-1个字符方案数为f[i-1][j-1]。两种选择互斥且互补因此相加得到状态转移方程$$ f[i][j]\left{ \begin{aligned} f[i-1][j], s[i-1] \ne t[j-1] \ f[i-1][j-1]f[i-1][j], s[i-1]t[j-1] \end{aligned} \right. $$边界与初始化当j 0t为空串时s的任何前缀都可以通过全部不取得到唯一的空子序列因此f[i][0] 1其中i ∈ [0, m]当i 0且j 0时空串无法构成非空子序列f[0][j] 0二维数组默认值即 0。复杂度分析时间复杂度O(m × n)需要遍历整个(m1) × (n1)的 DP 表空间复杂度O(m × n)使用二维数组存储全部状态。多语言实现以下实现与仓库源码逐一对应二维版源码见 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift。Python3class Solution: def numDistinct(self, s: str, t: str) - int: m, n len(s), len(t) f [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): f[i][0] 1 # t 为空串时只有一种空子序列 for i, a in enumerate(s, 1): for j, b in enumerate(t, 1): f[i][j] f[i - 1][j] # 不取 s[i-1] if a b: f[i][j] f[i - 1][j - 1] # 取 s[i-1] 匹配 t[j-1] return f[m][n]Javaclass Solution { public int numDistinct(String s, String t) { int m s.length(), n t.length(); int[][] f new int[m 1][n 1]; for (int i 0; i m 1; i) { f[i][0] 1; } for (int i 1; i m 1; i) { for (int j 1; j n 1; j) { f[i][j] f[i - 1][j]; if (s.charAt(i - 1) t.charAt(j - 1)) { f[i][j] f[i - 1][j - 1]; } } } return f[m][n]; } }Cclass Solution { public: int numDistinct(string s, string t) { int m s.size(), n t.size(); unsigned long long f[m 1][n 1]; memset(f, 0, sizeof(f)); for (int i 0; i m 1; i) { f[i][0] 1; } for (int i 1; i m 1; i) { for (int j 1; j n 1; j) { f[i][j] f[i - 1][j]; if (s[i - 1] t[j - 1]) { f[i][j] f[i - 1][j - 1]; } } } return f[m][n]; } };C 实现中用unsigned long long存储中间状态虽然题目保证最终答案在 32 位带符号整数范围内但转移过程中的中间累加值可能短暂超出int范围使用无符号 64 位类型可以稳妥地避免中间溢出。Gofunc numDistinct(s string, t string) int { m, n : len(s), len(t) f : make([][]int, m1) for i : range f { f[i] make([]int, n1) } for i : 0; i m; i { f[i][0] 1 } for i : 1; i m; i { for j : 1; j n; j { f[i][j] f[i-1][j] if s[i-1] t[j-1] { f[i][j] f[i-1][j-1] } } } return f[m][n] }TypeScriptfunction numDistinct(s: string, t: string): number { const m s.length; const n t.length; const f: number[][] new Array(m 1).fill(0).map(() new Array(n 1).fill(0)); for (let i 0; i m; i) { f[i][0] 1; } for (let i 1; i m; i) { for (let j 1; j n; j) { f[i][j] f[i - 1][j]; if (s[i - 1] t[j - 1]) { f[i][j] f[i - 1][j - 1]; } } } return f[m][n]; }SwiftSwift 中字符串不能按下标直接随机访问字符因此先将s、t分别转换为字符数组sArray、tArray再按统一的双重循环逻辑填充dp表class Solution { func numDistinct(_ s: String, _ t: String) - Int { let m s.count, n t.count let sArray Array(s) let tArray Array(t) var dp Array(repeating: Array(repeating: 0, count: n 1), count: m 1) for i in 0...m { dp[i][0] 1 } for i in 1...m { for j in 1...n { dp[i][j] dp[i - 1][j] if sArray[i - 1] tArray[j - 1] { dp[i][j] dp[i - 1][j - 1] } } } return dp[m][n] } }手工填表验证s rabbbitt rabbit以示例 1 为例手动推导一遍 DP 表可以直观理解转移过程。m 7n 6。初始化第一列f[i][0] 1i 0..7。逐行计算只列出非零关键值i \ j0123456010000001r11000002ra11100003rab11110004rabb11121005rabbb11133006rabbbi11133307rabbbit1113333关键步骤说明f[4][3] 2rabb中构成rab的子序列有 2 种使用第 1 个或第 2 个bf[5][3] 3rabbb中构成rab的方案增至 3 种f[5][4] 3同理f[7][6] f[6][5] f[6][6] 3 0 3最后字符t与t[5] t相等取匹配最后一位的 3 种方案s前 6 个字符rabbbi构成rabbi的 3 种方式最终答案正是 3。方法二动态规划优化一维滚动数组优化动机观察转移方程可以发现f[i][j]只依赖上一行的f[i-1][j]与f[i-1][j-1]与更早的行无关。因此可以去掉第一维i只用一维数组f[j]滚动保存当前行的状态空间复杂度从O(m × n)降至O(n)。为什么内层必须倒序更新一维化之后f[j]在更新前保存的是上一行的值f[i-1][j]更新后变成当前行的f[i][j]。而转移需要用到f[j-1]即上一行的f[i-1][j-1]若从小到大更新j则f[j-1]已被更新为当前行的值f[j] f[j-1]就错误地把同一行的新值加了进去导致重复计数若从大到小更新j则f[j-1]尚未被本轮更新仍是上一行的旧值正好符合转移方程对f[i-1][j-1]的需求。这就是一维滚动 DP 中倒序更新这一经典写法的本质原因。复杂度对比方案时间复杂度空间复杂度方法一二维 DPO(m × n)O(m × n)方法二一维滚动O(m × n)O(n)多语言实现一维版源码对应仓库中的 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts。Python3class Solution: def numDistinct(self, s: str, t: str) - int: n len(t) f [1] [0] * n # f[0]1 对应空 t其余初始为 0 for a in s: for j in range(n, 0, -1): # 必须倒序避免覆盖 f[j-1] 的上一行值 if a t[j - 1]: f[j] f[j - 1] return f[n]Javaclass Solution { public int numDistinct(String s, String t) { int n t.length(); int[] f new int[n 1]; f[0] 1; for (char a : s.toCharArray()) { for (int j n; j 0; --j) { char b t.charAt(j - 1); if (a b) { f[j] f[j - 1]; } } } return f[n]; } }Cclass Solution { public: int numDistinct(string s, string t) { int n t.size(); unsigned long long f[n 1]; memset(f, 0, sizeof(f)); f[0] 1; for (char a : s) { for (int j n; j; --j) { char b t[j - 1]; if (a b) { f[j] f[j - 1]; } } } return f[n]; } };Gofunc numDistinct(s string, t string) int { n : len(t) f : make([]int, n1) f[0] 1 for _, a : range s { for j : n; j 0; j-- { if b : t[j-1]; byte(a) b { f[j] f[j-1] } } } return f[n] }Go 版注意s是stringfor _, a : range s取出的a是rune因此比较时用byte(a) b转成字节后再与t[j-1]byte类型比较。TypeScriptfunction numDistinct(s: string, t: string): number { const n t.length; const f: number[] new Array(n 1).fill(0); f[0] 1; for (const a of s) { for (let j n; j; --j) { const b t[j - 1]; if (a b) { f[j] f[j - 1]; } } } return f[n]; }两种方法的选用建议方法一二维 DP思路直白、便于推导与口头讲解适合面试中先给出完整状态表再逐步引导优化的讲解节奏代价是当m n 1000时需开辟约10^6个状态单元。方法二一维滚动空间更优是竞赛与工程中的首选写法写代码时务必牢记内层j从n到1倒序更新这是该解法正确性的关键。两者在时间复杂度上同为O(m × n)无法进一步降低——因为每个状态都依赖上一行且必须全部计算。若t比s长f[m][n]恒为 0可以提前返回不过这属于可选的常数级剪枝。仓库源码索引与延伸学习本专题在仓库中的完整资源如下便于对照阅读与提交验证题目与双解法详解lcof2/剑指 Offer II 097. 子序列的数目/README.md二维 DP 实现Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift一维滚动优化实现Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts同题主站版本含 Rust 实现可作为语言覆盖补充solution/0100-0199/0115.Distinct Subsequences/README.md系列题解索引lcof2/README.mdRust 侧实现可参考主站 115 题中的写法见 Solution.rs其使用VecVecu64存储状态dp[i][0] 1完成空t初始化转移时按字符是否相等分别取dp[i-1][j]或dp[i-1][j] dp[i-1][j-1]与本文推导的状态转移方程完全一致最终as i32转回目标返回类型。通过本题可以提炼出一个通用的字符串计数 DP 模板凡是统计s中子序列等于t的方案数类问题都可以用f[i][j]表示前缀匹配方案数转移时按当前字符取或不取分情况讨论再视空间要求决定是否滚动为一维倒序更新。这一模板同样适用于其他子序列匹配计数型变体题目是面试中字符串动态规划的高频考察点。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐剑指 Offer II 104. 排列的数目动态规划求解有序组合计数的完整指南剑指 Offer II 104. 排列的数目动态规划求解有序组合计数的完整指南 导读 本文基于 doocs/leetcode 开源仓库中 《剑指 Offe示例工程LeetCode-Book《剑指 Offer》剑指 60n 个骰子的点数——正向动态规划状态转移与滚动数组空间优化LeetCode Book《剑指 Offer》剑指 60n 个骰子的点数——正向动态规划状态转移与滚动数组空间优化 本篇基于 LeetCode Book 仓库示例工程教程教育LeetCode 518. 零钱兑换 II 题解完全背包组合数计数型动态规划C 二维 DP 与一维滚动数组LeetCode 518. 零钱兑换 II 题解完全背包组合数计数型动态规划C 二维 DP 与一维滚动数组 本文是阿秀校招/社招刷题笔记「 精选力扣文档教程知识库上一篇Python Mastery数据备份增量备份与灾难恢复终极指南下一篇B站视频合集排序更新接口详解哔哩哔哩-API收集整理中的系列内容管理功能创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考