• 示例工程

导读

本文围绕《剑指 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 <= 1000
• s和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 到m（m = s.length），j从 0 到n（n = 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 = 0（t为空串）时，s的任何前缀都可以通过"全部不取"得到唯一的空子序列，因此f[i][0] = 1，其中i ∈ [0, m]；
• 当i = 0且j > 0时，空串无法构成非空子序列，f[0][j] = 0（二维数组默认值即 0）。

复杂度分析

• 时间复杂度：O(m × n)，需要遍历整个(m+1) × (n+1)的 DP 表；
• 空间复杂度：O(m × n)，使用二维数组存储全部状态。

多语言实现

以下实现与仓库源码逐一对应（二维版源码见 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift）。

Python3

class 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]

Java

class 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]; } }

C++

class 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 位类型可以稳妥地避免中间溢出。

Go

func numDistinct(s string, t string) int { m, n := len(s), len(t) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) } 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] }

TypeScript

function 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]; }

Swift

Swift 中字符串不能按下标直接随机访问字符，因此先将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 = "rabbbit"，t = "rabbit"）

以示例 1 为例手动推导一遍 DP 表，可以直观理解转移过程。m = 7，n = 6。

初始化第一列：f[i][0] = 1（i = 0..7）。

逐行计算（只列出非零关键值）：

关键步骤说明：

• f[4][3] = 2："rabb"中构成"rab"的子序列有 2 种（使用第 1 个或第 2 个b）；
• f[5][3] = 3："rabbb"中构成"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 中"倒序更新"这一经典写法的本质原因。

复杂度对比

多语言实现

一维版源码对应仓库中的 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts。

Python3

class 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]

Java

class 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]; } }

C++

class 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]; } };

Go

func numDistinct(s string, t string) int { n := len(t) f := make([]int, n+1) 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是string，for _, a := range s取出的a是rune，因此比较时用byte(a) == b转成字节后再与t[j-1]（byte类型）比较。

TypeScript

function 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.md

Rust 侧实现可参考主站 115 题中的写法（见 Solution.rs）：其使用Vec<Vec<u64>>存储状态，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]表示前缀匹配方案数，转移时按"当前字符取或不取"分情况讨论，再视空间要求决定是否滚动为一维倒序更新。这一模板同样适用于其他"子序列匹配计数"型变体题目，是面试中字符串动态规划的高频考察点。

• 示例工程