代码随想录算法训练营Day54 | 392.判断子序列 115.不同的子序列

本文主要是介绍代码随想录算法训练营Day54 | 392.判断子序列 115.不同的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营Day54 | 392.判断子序列 115.不同的子序列

LeetCode 392.判断子序列

题目链接：LeetCode 392.判断子序列

思路：
和最长子序列等价

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size();int n = t.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i=1; i<=m; i++){for(int j=1; j<=n; 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[m][n] == m) return true;else return false;}
};

注意：

题目是判断s是否为t的子序列，只需要判断最长公共子序列是否等于s的长度即可。

LeetCode 115.不同的子序列

题目链接：LeetCode 115.不同的子序列

思路：
dp [i][j] 依次删除元素

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