昨天因为志愿活动和笔试耽误了一整天，今天继续学习动规解决子序列问题。

392.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

思路：

1.本题又涉及到对于两个字符串，判断其中一个是不是对方的子序列了。有了前面部分的基础后本题的思路还是比较好想了。

2.首先想dp数组含义，dp[i][j]表示字符串s中以i-1结尾，t中以j-1结尾的最长子序列长度。

3.然后想递推公式。根据dp数组含义，我们比较s[i - 1]和t[j - 1]的字符，如果相等，那么dp[i][j] = dp[i - 1][j - 1] + 1，相当于在之前最长子序列长度之上加一；如果不相等，那么dp[i][j] = dp[i][j - 1]（注意，本题是确定s是t的子序列，因此如果涉及删除操作只会删除t而不会删除s，与Day57的最长公共子序列进行区分）

4.然后想初始化。由递推公式不难看出，dp[i][j]只可能由其左边的元素和斜左上方的元素推出来，因此ddp[0][j]和dp[i][0]均需要初始化成0.

5.最后想遍历顺序，由递推公式可以看出一定是从左向右，从上向下遍历。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

        for(int i = 1; i <= s.size(); i++){
            for(int j = 1; j <= t.size(); j++){
                if(s[i - 1] == t[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else{
                    dp[i][j] = dp[i][j - 1];
                }
                cout << dp[i][j] << ",";
            }
        }

        return s.size() == dp[s.size()][t.size()];
    }
};

启发：

1.本题再一次熟悉了关于二维dp数组存储两个数组/字符串状态的思路，以及寻找子序列时要判断哪一方是可以进行删除的一方。本题建议打印出dp数组好好理解一番。

115.不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

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

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

思路：

1.本题是目前遇到的最难的一道子序列题，即使看完了讲解个人在打印出dp数组后也比较难完全理解本题的一个思路。

2.首先想dp数组含义，dp[i][j]表示以i - 1结尾的字符串s中包含有以j-1结尾的字符串t的个数。

3.然后想递推公式，本题最难的地方就在于理解递推公式。当s[i - 1] == t[j - 1]时，我们分为两种情况：一种情况是不考虑s[i - 1]和t[j - 1]，因为这俩已经相等了，我们用[0, i -2]和[0, j -2]的部分进行匹配，即dp[i - 1][j - 1]；另一种情况是不考虑s[i - 1]，此时对应dp[i - 1][j]。

最不理解的地方在于为什么在相等的情况下还存在不考虑s[i - 1]的情况，这里引用代码随想录中的讲解：

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

更进一步，我们可以想想之前的跳楼梯类型题目。我们一定要弄清楚算的是跳了多少步，还是一共有几种跳的方法。对于计算跳的方法，我们只需要加上前面的方法就可以了，不需要再加某些常数之类的东西，因为跳到当前台阶的方法实际上就是到达前面台阶的方法数（此时只需要在前面台阶的基础上跳n级就可以了，但方法数实际上就是前面台阶的方法数）；而如果是算跳了多少步，此时显然还需要再加一个1。

本题实际上是类似于算跳楼梯有几种跳的方法，针对于s[i - 1]和t[j - 1]相等时的情况，我们可以同时不考虑s[i - 1]和t[j - 1]，因为这两者已经确定相同了，我们只需要看二者前一个位置相匹配的所有子序列个数就可以了（无非是在最后的子序列尾巴加入当前的s[i - 1]，但是不影响个数）。

不过最难得还是想到当s[i - 1] == t[j - 1]时还存在只不考虑s[i - 1]的情况。

而对于s[i - 1] != t[j - 1]的情况，我们就模拟将s[i - 1]删除，即dp[i][j] = dp[ i -1][j]。

4.然后想初始化，本题初始化也很有讲究。对于dp[i][0]，实际上是算对于以i-1结尾的字符串s中有多少个空字符串，将s全部删除后实际上必定是得到一个空字符的，因此dp[i][0] = 1；而对于dp[0][j]，实际上是算对于空字符s中有多少个以j -1结尾的字符串t，显然是不可能包含的，因此dp[0][j] = 0。关于最特殊的dp[0][0]，即空字符串中包含有多少空字符串，我们将其初始化为1。

5.最后是遍历顺序，由递推公式我们可以看出dp[i][j]只能由其斜左上方或者上方推导出来，因此遍历顺序一定是从左往右，从上往下。

class Solution {
public:
    int numDistinct(string s, string t) {
        //dp数组含义，以i - 1结尾的s字符串中包含的以 j - 1结尾的t字符串的个数
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

        //dp[i][0]表示以i - 1结尾的s字符串中包含的空字符串个数
        for(int i = 0; i <= s.size(); i++){
            dp[i][0] = 1;
        }
        
        for(int i = 1; i <= s.size(); i++){
            for(int j = 1; j <= t.size(); 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];
                }
                cout << dp[i][j] << ",";
            }
            cout << endl;
        }

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

启发：

1.本题一下子就上了难度，对于s[i - 1] == t[i - 1]的两种情况还需要进一步结合爬楼梯问题理解这么做的思路，本题强烈建议打印dp数组看整个推导的过程。