115. Distinct Subsequences

问题

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

例子

S = "rabbbit", T = "rabbit"
Return 3.

分析

题目的意思是，通过删除字符，S有多少种方法可以变成T.

动态规划：

1. 状态表
   dp[i][j]，表示S[0, i - 1]有dp[i][j]种方法可以变成T[0, j - 1]
2. 初始状态
   dp[0][0] = 1 空字符串只有一种方法变成空字符串（不进行任何操作）
   dp[i][0] = 1, i >= 1 字符串只有一种方法变成空字符串（删除所有字符）
   dp[0][j] = 0, j >= 1 空字符串没法变成非空字符串
3. 状态转移方程
   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], if S[i - 1] != T[j - 1]
   注：当S[i - 1] == T[j - 1]时，可以有两种变化方法可以选择：一种是删除S[i - 1]，用S[0, i - 2]变成T[0, j - 1]，有dp[i - 1][j]种方法；还有一种是保留S[i - 1]，用S[0, i - 2]变成T[0, j - 2]，有dp[i - 1][j - 1]种方法。当S[i - 1] != T[j - 1]时，只能删除S[i - 1]。

要点

dp

时间复杂度

O(mn)

空间复杂度

O(mn) or O(m) or O(n)

代码

Space Complexity O(mn)

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++)
            dp[i][0] = 1;
        for (int j = 1; j <= n; j++)
            dp[0][j] = 0;
            
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
};

Space Complexity O(n)

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        
        for (int i = 1; i <= m; i++) {
            int pre = dp[0];
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (s[i - 1] == t[j - 1])
                    dp[j] += pre;
                pre = temp;
            }
        }
        return dp[n];
    }
};