392.判断子序列
跟昨天做的两道题也很像，用昨天的代码也可以写出来。我自己又重新手写了一遍，出现了一个小马虎，就是在最后DP的值是否等于 s的长度的时候，我写成了dp[s.length()-1][t.length()-1]，但其实应该用dp[s.length()][t.length()]，因为在这道题里我们设了一个比s和t都大一个的二维数组。
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp (s.length()+1,vector<int>(t.length()+1,0));
for(int i=1; i<=s.length(); i++){
for(int j=1; j<=t.length(); j++){
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
if(dp[s.length()][t.length()] == s.length()){
return true;
}
else{
return false;
}
}
};
115.不同的子序列
这道题自己没想出来。但是现在基本上理解了。
首先是dp的含义，dp是当前应有多少种答案。详细点解释就是：当s的长度i,t的长度为j时，dp[i][j]表示有多少种结果。
然后是初始化，外循环是长的string，内循环是短的string。因为我们要遍历完一遍长的string才知道到底有多少种结果。所以当s（短的）为0的时候，那么不管t(长的)有多少长，就应该有1种答案。如果t是0，那么就不应该有任何答案，也就是等于0。
然后我们对于dp的取值：当两个数一样的时候，那dp就应该等于左上方的值和上方的值。左上方的值代表之前有多少个数一致，上方旳值是继承之前找到了多少种答案。
具体的逻辑还需要再多想想。
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
for (int j = 1; j < t.size(); j++) dp[0][j] = 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] + dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.size()][t.size()];
}
};
