不同的子序列如何用动态规划计数？为什么匹配时要加上“不用当前字符”的方案？

简化版

不同的子序列用 dp[i][j] 表示 s 的前 i 个字符中，有多少种子序列等于 t 的前 j 个字符。若 s[i-1] == t[j-1]，当前字符可以用也可以不用，所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；不相等时只能不用当前字符。

详细版

初始化时，任何字符串变成空串都有 1 种方式，也就是删除所有字符，所以 dp[i][0]=1；空串无法组成非空目标串，所以 dp[0][j]=0。转移时要分清“选当前 s[i-1] 去匹配 t[j-1]”和“不选当前字符”两类方案。

时间复杂度 O(mn)，空间复杂度可以优化为 O(n)。如果计数可能很大，要关注语言中的整数范围，工程里可能需要 long 或取模；原题通常保证结果在范围内。

完整版教学

一、子序列计数和普通匹配有什么不同

子序列允许删除字符，但不能改变相对顺序。例如 s="rabbbit"，t="rabbit"，可以删除三个 b 里的任意一个，得到 3 种不同方案。这里问的不是能不能匹配，而是方案数量。

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

计数题的关键是把互不重叠的选择分类，避免漏算或重复算。

二、状态定义为什么用两个前缀

定义：

dp[i][j] = s[0..i-1] 的子序列中，等于 t[0..j-1] 的方案数

用前缀是因为子序列保持相对顺序。处理到 s[i-1] 时，只需要知道前面的字符能组成多少目标前缀。

状态	含义
`dp[i][j]`	用 s 的前 i 个字符匹配 t 的前 j 个字符
`dp[i-1][j]`	不使用当前 s 字符
`dp[i-1][j-1]`	使用当前 s 字符匹配当前 t 字符

这个定义自然包含“删字符”的动作：不用当前字符就是删除它。

三、初始化为什么 `dp[i][0]=1`

目标串为空时，任何 s 前缀都有 1 种方式匹配它：什么都不选。比如 s="abc" 要形成空串，唯一方案是删掉 a,b,c。

dp[0][0] = 1
dp[1][0] = 1
dp[2][0] = 1
dp[3][0] = 1

而 dp[0][j] 对 j>0 是 0，因为空的 s 不可能形成非空的 t。

记忆钩子：计数 DP 里，空目标通常有 1 种“什么都不选”的方案。

四、字符相等时为什么是两个来源相加

当 s[i-1] == t[j-1]，当前字符有两种互斥选择：

1. 用它匹配 t[j-1]：dp[i-1][j-1]
2. 不用它，继续让前 i-1 个字符匹配 t 前 j 个：dp[i-1][j]

所以：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

这不是取最大值，因为题目要的是方案数；两个集合互不重叠，一个使用当前字符，一个不使用当前字符。

五、字符不相等时为什么只能继承

如果 s[i-1] != t[j-1]，当前 s 字符无法匹配当前 t 字符，只能跳过它：

dp[i][j] = dp[i-1][j]

例如 s 当前是 x，t 当前需要 b，你不能强行用 x 参与匹配。子序列允许删除，所以跳过当前字符是唯一合法选择。

这个地方不能写成 dp[i][j-1]，因为那表示少匹配一个目标字符，语义已经变了。

六、代码和空间优化

二维写法最清晰：

int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[][] dp = new long[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    return (int) dp[m][n];
}

一维优化时，j 必须倒序遍历，避免 dp[j-1] 被本轮提前更新。

for c in s:
    for j from n down to 1:
        if c == t[j-1]: dp[j] += dp[j-1]

七、常见误区与追问

误区：字符相等时只取 dp[i-1][j-1]。 这样漏掉“不使用当前字符”的方案。
误区：把计数题写成取最大值。 本题要统计方案数量，不是求最长或最优。
误区：一维优化时正序遍历。 正序会让当前字符被同一轮重复使用。
追问：为什么空目标是 1 种方案？ 因为选择空子序列也是一种合法选择。
追问：结果会不会溢出？ 实际工程要用更大整数或取模，原题通常约束答案范围。
追问：子串和子序列有什么区别？ 子串必须连续，子序列只保持相对顺序。

八、加强记忆

不同的子序列要记住“当前字符用不用”这把刀。相等时分成使用和不使用两类，所以相加；不等时只能不使用，所以继承上方。初始化里空目标为 1 是计数 DP 的地基。一维优化必须倒序，因为每个 s 字符在一轮里只能贡献一次。

简化版

详细版