本文主要是介绍代码随想录算法训练营第五十四天|LeetCode392 判断子序列、LeetCode115 不同的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
392.判断子序列
思路：本质还是寻找s与t的最长公共子序列，如果最长公共子序列长度与s的长度相同，说明s为t的子序列。因此确定dp数组及其下标含义dp[i][j]为以s[i-1]和t[j-1]的子序列的最长公共子序列长度，递推公式,如果s[i-1]==t[j-1]，dp[i][j] = dp[i-1][j-1]+1.如果不相等，dp[i][j] = dp[i][j-1],因为s整段都需要判断，因此不能考虑s删元素的情况，只考虑t删元素的情况。初始化dp数组，都为零，第-1个元素没意义。遍历顺序，从小到大。
class Solution {
public:bool isSubsequence(string s, string t) {//判断两个公共子序列的最大长度是不是 短序列的长度//dp[i][j]表示以s[i-1]和t[j-1]为结尾的两个序列的最长公共序列长度 这样定义方便初始化//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])int size1 = s.size();int size2 = t.size();vector<vector<int>> dp(size1+1,vector<int>(size2+1,0));int maxnum = 0;for(int i = 1;i<=size1;i++){for(int j =1;j<=size2;j++){if(s[i-1]==t[j-1]){dp[i][j] = dp[i-1][j-1]+1;maxnum = maxnum>dp[i][j]?maxnum:dp[i][j];}else{dp[i][j] = dp[i][j-1];}}}if(maxnum == size1){return true;}else{return false;}}
};115.不同的子序列
思路：仍然是判断s和t的序列关系，跟上道题的递推公式有些相似，首先定义dp数组及其下标含义dp[i][j]表示以s[i-1]结尾的序列包含以t[j-1]结尾的序列的最大个数。递推公式：如果s[i-1]==t[j-1]有两种情况，第一种考虑s[i-1]，最大个数为dp[i-1][j-1]，第二种不考虑s[i-1],最大个数为dp[i-1][j]。因此dp[i][j] = dp[i-1][j-1]+dp[i-1][j].如果s[i-1]!=t[j-1]，直接不考虑s[i-1].dp[i][j] = dp[i-1][j].初始化dp数组，dp[i][0]，s字符串（无论是否为空）一定包含空字符串t，dp[0][j]=0，字符串s为空，t非空时，一定不包含t。遍历顺序，从小到大。
class Solution {
public:int numDistinct(string s, string t) {//确定dp数组及其下标含义 dp[i][j] 表示以s[i-1]结尾的字符串包含 以t[j-1]结尾的字符串的个数//递推公式 如果s[i-1]==t[j-1],dp[i][j]由两种情况组成//1、使用s[i-1]，dp[i][j] = dp[i-1][j-1]; 个数为以s[i-2]和t[i-2]结尾的字符串包含个数//2、不使用s[i-1]，dp[i][j] = dp[i-1][j]; 个数为以s[i-2]和t[i-1]结尾的字符串包含个数//dp[i][j] = dp[i-1][j-1]+dp[i-1][j];//初始化dp数组//dp[i][0]=1 和dp[0][j] = 0，因为s一定包含空字符串，而空字符串不会包含非空字符串。int size1 = s.size();int size2 = t.size();vector<vector<uint64_t>> dp(size1+1,vector<uint64_t>(size2+1,0));for(int i = 0;i<size1;i++){dp[i][0]=1;}for(int i =1;i<=size1;i++){for(int j =1;j<=size2;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[size1][size2];}
};int类型数据会溢出，使用uint64_t.
这篇关于代码随想录算法训练营第五十四天|LeetCode392 判断子序列、LeetCode115 不同的子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
