线性动态规划：不同的子序列

题目描述

给定两个字符串 s 和 t，请统计在 s 的子序列中等于 t 的个数（注意是子序列，不是子串）。
子序列的定义是：从原字符串中删除一些（或不删除）字符，而不改变剩余字符的相对顺序形成的新字符串。

示例 1
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
以下为 s 中可得到 "rabbit" 的三种子序列（^ 表示选取的字符）：

r a b b b i t
^ ^ ^ ^   ^ ^
r a b b b i t
^ ^ ^   ^ ^ ^
r a b b b i t
^ ^   ^ ^ ^ ^

示例 2
输入：s = "babgbag", t = "bag"
输出：5
解释：略。

解题过程

第一步：问题分析

我们要在字符串 s 中找出等于 t 的子序列的个数。
注意：

• 子序列不一定连续。
• 不同的选取位置即使得到相同的子序列，也算作不同的方案（因为从原串的不同位置选取）。
• 当 t 是空串时，任何 s 都有一个空子序列与之匹配，所以答案是 1。

第二步：定义状态

用动态规划来思考，我们通常从两个字符串的前缀入手。

定义：

• dp[i][j] 表示：在 s 的前 i 个字符中（即 s[0..i-1]），t 的前 j 个字符（即 t[0..j-1]）出现的子序列个数。
• 这里 i 表示 s 的前 i 个字符，j 表示 t 的前 j 个字符，i 和 j 从 0 开始到它们的长度。

初始条件：

• 如果 j = 0，即 t 是空串，那么无论 s 是什么，都只有一种方案：不选任何字符，所以 dp[i][0] = 1。
• 如果 i = 0 且 j > 0，即 s 是空串，t 非空，则无法匹配，dp[0][j] = 0。

第三步：状态转移方程

考虑当前比较 s[i-1] 和 t[j-1]。

1. 如果 s[i-1] != t[j-1]：
   当前 s 的第 i 个字符不能用于匹配 t 的第 j 个字符，那么只能“跳过” s[i-1]，看看前面 i-1 个字符匹配 t 的前 j 个字符的情况，即：
   dp[i][j] = dp[i-1][j]。

2. 如果 s[i-1] == t[j-1]：
   此时有两种选择：

   • 用 s[i-1] 去匹配 t[j-1]：那么就要看前面 s[0..i-2] 匹配 t[0..j-2] 的方案数，即 dp[i-1][j-1]。
   • 不用 s[i-1] 匹配，跳过它：那么看 s[0..i-2] 匹配 t[0..j-1] 的方案数，即 dp[i-1][j]。
     因此总方案数是二者之和：
     dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。

综上：

if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
    dp[i][j] = dp[i-1][j]

第四步：边界与初始化

• dp[i][0] = 1 对所有 i 成立（空 t 匹配任何 s）。
• dp[0][j] = 0 对 j ≥ 1 成立（空 s 无法匹配非空 t）。

我们可以创建一个二维数组 dp，维度为 (len(s)+1) x (len(t)+1)，然后按上述规则填充。

第五步：举例推导

以 s = "rabbbit", t = "rabbit" 为例（长度分别为 7 和 6）。

初始化：

dp[i][0] = 1
dp[0][j] = 0 (j>0)

逐步计算（只写几个关键点）：

• i=1, s[0]='r', j=1, t[0]='r'：相等 → dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0 = 1
• ……
  最终填表，得到 dp[7][6] = 3。

第六步：空间优化

注意到 dp[i][j] 只依赖于上一行 i-1 的值，因此可以用滚动数组优化空间，只用两行（或一维数组从后往前更新）。

用一维数组 dp[j] 表示当前匹配 t 的前 j 个字符的方案数，更新时从 j = len(t) 到 1 反向更新（避免覆盖上一轮的结果）：

伪代码：

初始化 dp[0] = 1, dp[1..len(t)] = 0
for i from 1 to len(s):
    for j from len(t) down to 1:
        if s[i-1] == t[j-1]:
            dp[j] += dp[j-1]
        # 否则 dp[j] 不变（相当于用上一轮的 dp[j]，因为反向更新保留了它）

注意：当 s[i-1] != t[j-1] 时，dp[j] 不变，就是 dp[i-1][j] 的值，反向更新时它还在。

第七步：最终代码框架（Python）

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, m + 1):
        # 反向更新
        for j in range(n, 0, -1):
            if s[i-1] == t[j-1]:
                dp[j] += dp[j-1]
    return dp[n]

第八步：复杂度分析

• 时间复杂度：O(m × n)，m 和 n 分别是 s 和 t 的长度。
• 空间复杂度：O(n)，用了滚动数组优化。

总结

这道题是“不同的子序列”计数问题，核心在于状态定义和转移时考虑用与不用当前字符两种情况。
关键是理解：当字符相等时，方案数 = 用当前字符匹配的方案数 + 不用当前字符匹配的方案数。
最终结果在 dp[len(s)][len(t)] 中。