一、leetcode第392题
本题要求判断s是否为t的子序列,因此设置dp数组,dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数,可得递推公式是通过s[i-1]和t[j-1]是否相等区分。
具体代码如下:
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]=dp[i][j-1];}}}if(dp[s.length()][t.length()]==s.length()){return true;}return false;}
};
二、leetcode第115题
本题要求s的子串与t相等的个数,因此设置dp数组,其中dp[i][j]的含义是i-1为下标的子串中包含j-1为下标的子串的个数,根据s[i-1]和t[j-1]是否相等来写递推公式,相等时递推公式dp[i][j]由dp[i-1][j-1](考虑s[i-1])和dp[i-1][j](不考虑s[i-1])构成,不相等时则等于不考虑s[i-1]时的递推式。
具体代码如下:
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>>dp(s.length()+1,vector<uint64_t>(t.length()+1));for(int i=0;i<=s.length();i++){dp[i][0]=1;}for(int j=1;j<=t.length();j++){dp[0][j]=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]+dp[i-1][j];}else{dp[i][j]=dp[i-1][j];}}}return dp[s.length()][t.length()];}
};