1、思路

• dp[i][j]表示字符串s[0 ... i]的子字符串中等于字符串t[0 ... j]的子序列数目；

• 初始化：
  1、dp[0][0] = 1，空字符串能组成空字符串；
  2、dp[0][1 ... m] = 0，空字符串无法组成任何非空字符串；
  3、dp[1 ... n][0] = 1，非空字符串可以有一种方式组成空字符串；

• 当s[i] == t[j]时，分两种情况讨论：
  1、用s[i]去匹配t[j]，那么dp[i][j] = dp[i - 1][j - 1]；
  2、舍去s[i]，那么dp[i][j] = dp[i - 1][j]，总结下来就是dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]；

• 时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。

2、代码

class Solution {
public:
    int numDistinct(string s, string t) {
        if (s.length() < t.length()) return 0;

        vector<vector<unsigned int>> dp(s.length() + 1, vector<unsigned int>(t.length() + 1, 0));

        dp[0][0] = 1;       //初始化1
        for (int i = 1; i <= s.length(); ++ i)
        {                   //初始化2：数组元素默认已经是0，不用显式地初始化了
            dp[i][0] = 1;   //初始化3
            for (int j = 1; j <= i && j <= t.length(); ++ 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];                    //第二种情况
                }
            }
        }

        return dp[s.length()][t.length()];
    }
};

3、优化空间复杂度

• 当前状态只与最近两行的状态有关，所以可以用一个2行的二维数组（滚动数组）来存储状态；

• 时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。

class Solution {
public:
    int numDistinct(string s, string t) {
        if (s.length() < t.length()) return 0;

        vector<vector<unsigned int>> dp(2, vector<unsigned int>(t.length() + 1, 0));

        dp[0][0] = 1;
        for (int i = 1; i <= s.length(); ++ i)
        {
            dp[i % 2][0] = 1;
            for (int j = 1; j <= i && j <= t.length(); ++ j)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i % 2][j] = dp[(i + 1) % 2][j - 1] + dp[(i + 1) % 2][j];
                }
                else
                {
                    dp[i % 2][j] = dp[(i + 1) % 2][j];
                }
            }
        }

        return dp[s.length() % 2][t.length()];
    }
};