392.判断子序列

// dp[i][i] s[0到i-1]和s[0到j-1]的最大相同子序列长度
// if (s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
// else dp[i][j]=dp[i][j-1];注意，我们只是在对比j中的情况，所以是j-1
// dp[0][0]=0
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()+1; i++){for (int j=1; j<t.size()+1; 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];}}if (dp[s.size()][t.size()]==s.size()) return true;return false;}
};

注意dp数组的可视化如下，dp的大小为dp(s.size()+1, vector(t.size()+1, 0));

115.不同的子序列

dp[i][j]的含义是s[0:i]和t[0:j]有多少个匹配的子序列
dp[i-1][j]表示s[0:i-2]，t[0:j-1]中已经出现匹配的子序列的个数，当新获取的s[i-1]==t[j-1]时，自然这个相等的新元素可以继承前面以同样元素结尾的结果。dp[i-1][j-1]表示在新加入的元素s[i-1]==t[j-1]之前，是没有符合的子序列的，当这个新元素加入后才第一次出现匹配的子序列。

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1, 0));for (int i=0; i<s.size(); i++){dp[i][0]=1;}for (int i=1;i<s.size()+1; i++){for (int j=1; j<t.size()+1; 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.size()][t.size()];}
};