不同的子序列 图解题解

不同的子序列这道题到底在数什么

给字符串 s 和 t，要在 s 里按原先后顺序挑字符、拼出和 t 一样的串，问有多少种不同挑法。子序列（从原串挑若干字符、保持先后、可跳过）不要求连续，但顺序不能乱。题面 s="rabbbit"、t="rabbit" 答案 3，三种挑法只差在中间三个 b 挑哪两个。

把 s 的子序列全列出来为什么行不通

s 每个字符可挑可不挑，长 n 就有 2 的 n 次方个子序列，逐个和 t 比对便是天文数字。而且相同前缀的子序列被反复重拼、同一中间结果本该只算一次。把「s 前若干个字符能凑 t 前若干个字符」记下复用，指数级枚举就压成一张表逐格递推（用已算好的格子推出当前格）。

dp[i][j] 该定成什么，第 0 列为什么全填 1

这题用动态规划（把「s 前若干个字符能凑 t 前若干个字符有几种挑法」逐格存表、直接取不重算）。定义 dp[i][j]（i、j 从 0 数起，i 行 j 列）为「s 前 i 个字符里能凑出 t 前 j 个字符的挑法数」。铺边界：第 0 列 dp[i][0] 全是 1——凑空的 t 什么都不挑、唯一一种；第 0 行 dp[0][j]（j≥1）全是 0——s 空串凑不出非空 t。

字符相等时，为什么要把两条路相加

填 dp[i][j] 时只盯 s[i-1]（s 的第 i 个字符，下标从 0 数起）和 t[j-1]。两者不相等时，s 这个字符配不上 t 要的位、只能弃用，照搬正上方 dp[i-1][j]。

相等时有两条互不重叠的路、方案数相加。一条：用它当 t 的第 j 位，前面得用 s 前 i-1 个凑出 t 前 j-1 位，是左上角 dp[i-1][j-1]；另一条：不用它，仍靠 s 前 i-1 个凑完整的 t 前 j 位，是正上方 dp[i-1][j]。「用」和「不用」互不重叠、不会重复计数，所以 dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。

拿 rabbbit 和 rabbit 亲手把表填出来

表是 8 行 7 列（s 长 7、t 长 6 各加边界行列）。第 0 列全 1、余下全 0。方案数靠三个 b 长起来：（前面 r 配 r、a 配 a 各只有 1 种，落到 dp[2][2]=1；dp[2][3]=0）dp[3][3]=dp[2][2]+dp[2][3]=1+0=1，dp[4][3]=dp[3][2]+dp[3][3]=1+1=2，dp[5][3]=dp[4][2]+dp[4][3]=1+2=3。收尾 dp[7][6]=dp[6][5]+dp[6][6]=3+0=3，正是用整个 rabbbit 凑出 rabbit 的总数，对上题面。

第 0 列少填一个 1，整张表为什么一路塌成 0

整张表 (m+1)×(n+1) 格，每格一次比较一次加法，时间 O(m×n)；填当前行只用得上正上方一行，把二维表压成一行就地覆盖（滚动数组），空间降到 O(n)。

最易写错的是第 0 列：漏填或错成 0，相等时「用这个字符」那条路接左上角就恒为 0、整张表塌成全 0，答案错成 0。第 0 行相反，s 空凑非空 t 必须是 0，误填 1 会多出挑法。

Python

def numDistinct(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for r in range(m+1):
        dp[r][0] = 1
    for r in range(1, m+1):
        for c in range(1, n+1):
            if s[r-1] == t[c-1]:
                dp[r][c] = dp[r-1][c-1] + dp[r-1][c]
            else:
                dp[r][c] = dp[r-1][c]
    return dp[m][n]

C++

int numDistinct(string s, string t){
    int m = s.size(), n = t.size();
    vector<vector<unsigned long long>> dp(m+1, vector<unsigned long long>(n+1, 0));
    for(int r = 0; r <= m; r++) dp[r][0] = 1;
    for(int r = 1; r <= m; r++)
        for(int c = 1; c <= n; c++)
            if(s[r-1] == t[c-1]) dp[r][c] = dp[r-1][c-1] + dp[r-1][c];
            else dp[r][c] = dp[r-1][c];
    return (int)dp[m][n];
}

Java

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