leetcode：115. 不同的子序列

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。

示例：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

解答 & 代码

二维动态规划（dp）：

动态规划数组 dp：dp[i][j] 代表 s 的前 i 个字符 s[0, ..., i-1] 的子序列中有多少个是 t 的前 i 个字符 t[0, ..., j-1]
状态转移方程：
初始化：
- dp[0][0] = 1：s 的前 0 个字符为空，子序列也只有空这一个，t 的前 0 个字符也为空，因此为 1
- dp[0][j] = 0：s 的前 0 个字符为空，子序列也只有空这一个，而 t 的前 j 个字符不为空，因此为 0
- dp[i][0] = 1：s 的子序列中包含一个空（即删除所有字符），t 的前 0 个字符为空，因此为 1

注意：dp 数组存储的元素应为 **unsigned long long**，因为虽然题目保证结果为 int，但是中间结果可能溢出

class Solution {
public:
    int numDistinct(string s, string t) {
        int sLen = s.size();
        int tLen = t.size();
        // 动态规划数组 dp：dp[i][j] 代表 s 的前 i 个字符 s[0, ..., i-1] 的子序列中
        // 有多少个是 t 的前 i 个字符 t[0, ..., j-1]
        vector<vector<unsigned long long>> dp(sLen + 1, vector<unsigned long long>(tLen + 1, 0));
        // 初始化
        for(int i = 0; i <= sLen; ++i)
            dp[i][0] = 1;

        // 状态转移
        for(int i = 1; i <= sLen; ++i)
        {
            for(int j = 1; j <= tLen; ++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[sLen][tLen];
    }
};

复杂度分析：设字符串 s 长为 m，字符串t 长为 n

时间复杂度 O(mn)：
空间复杂度 O(mn)：

执行结果：

执行结果：通过

执行用时：48 ms, 在所有 C++ 提交中击败了 22.02% 的用户
内存消耗：29.4 MB, 在所有 C++ 提交中击败了 52.45% 的用户

hot 100

[困难] 115. 不同的子序列

题目

解答 & 代码