今天太晚了，先写一题，剩下的明天补。

115.不同的子序列

这个一看是困难题我就直接去看视频讲解了，总结一下，这道题还是很难的。
首先这道题涉及到不连续的子序列，根据之前的经验，我第一时间想到dp数组的定义应该是考虑s[0, i]范围内，t[0,j]有dp[i][j]个，但是实际上不是这样，而是以i结尾，j结尾的套路，第一步就给我干傻了。这道题的dp数组构造还是挺难理解的，这道题dp数组的含义是：字符串s考虑以s[i - 1]结尾的字符串中, 字符串t以t[j - 1]结尾的字符串有dp[i][j]个，感觉定义就很晦涩难懂。
其次是状态转移方程，说实话我打死都想不到能这样，当s[i - 1] == t[j - 1]时，dp[i][j]不光与dp[i - 1][j - 1]有关，还和dp[i - 1][j]有关，考虑这么一个例子：
s = “bbag” , t = “bag”，当i遍历到第二个b时，如果只考虑dp[i - 1][j - 1],那么就会漏掉第一个b也匹配的情况，所以必须把这种情况考虑进去，至于为什么不考虑dp[i][j - 1]，原因就在于这道题是问我们s中有多少个t，而不是t中有多少个s，所以不用考虑。
当s[i - 1] != t[j - 1]时,dp[i][j] = dp[i - 1][j]，这是因为当前s的字符串不匹配，不代表s之前的字符串也一定不匹配，后面的情况必须要包含前面的情况。
初始化这里我感觉dp[i][0]的初始化还是讲的有点晦涩，感觉根据定义给出的解释太牵强了。建议还是把初始状态带进去，看看遍历s和t的首字符的情况下，需要用到的变量应该是什么样子，再根据需要对其进行初始化。
我感觉最恶心的还是题目给的输入，给的输入数值非常大，我本以为对最后返回的dp[m][n]求个余就完事了，没想到中间就直接溢出了，必须用long long 才能不报错，在中间更新dp数组的时候就必须进行求余操作，我觉得没必要这样恶心人啊。

class Solution {
public:
    int numDistinct(string s, string t) {
        //1.确定dp[i][j]的含义：字符串s考虑以s[i - 1]结尾的字符串中, 
        //  字符串t以t[j - 1]结尾的字符串有dp[i][j]个
        //2.确定递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        //          or dp[i][j] = dp[i - 1][j];
        //3.dp数组初始化 dp[0][j] = 0;
        //              dp[i][0] = 1;(dp[0][0] == 1)
        //4.确定遍历顺序：从左往右，从上往下遍历
        //5.打印数组(省略)
        int m = s.size();
        int n = t.size();
        vector<vector<long long>> dp(m + 1, vector<long long> (n + 1, 0));
        //初始化
        for(int i = 0; i < m; i++)
            dp[i][0] = 1;
        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 - 1] + dp[i - 1][j]) % (long)(pow(10.0, 9) + 7);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
};

今天先这样，下播。