392. 判断子序列
思路:
判断子序列可以转化成s、t的最长公共子序列是不是s的问题。dp[i][j]为s的在第i-1处和t在j-1处最长公共子序列为dp[i][j]。递推关系：如果s[i-1]==t[j-1],dp[i][j]=dp[i-1][j-1]+1，如果二者不相等，dp[i][j]=dp[i][j-1]（比较前一个元素和当前s中的元素是否相等）。初始化：dp[0][i]=0,dp[j][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();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];
}
}
if(dp[s.size()][t.size()]==s.size())
{
return true;
}else return false;
}
};
115. 不同的子序列
思路：
这道题和上一道题的区别在于求解获得子序列有多少种方式。dp[i][j]:下标为i-1的字符串s中出现下标为j-1的字符串t的数量为dp[i][j]。递推关系：如果s[i-1]==t[j-1]，dp[i][j]可以是dp[i-1][j-1](dp[i-1][j-1]的含义是下标为i-2的字符串s中出现下标为j-2的字符串t的数量为dp[i-1][j-1]),也可以是dp[i-1][j](dp[i-1][j]的含义是下标为i-2的字符串s中出现下标为j-1的字符串t的数量为dp[i-1][j])，由定义可知dp[i][j]应该是两个值的和。如果s[i-1]!=t[j-1],dp[i][j]可以是dp[i-1][j]。初始化：dp[0][j]=0,dp[i][0]=1;dp[0][0]=1;遍历顺序：从小到大。
代码：
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()];
}
};
