【C++编程能力提升】

代码随想录训练营Day57 | Leetcode 392、115

• 一、392 判断子序列
• 二、115 不同的子序列

一、392 判断子序列

题目链接：392 判断子序列

核心：dp[i][j]表示以i-1结尾的s和以j-1结尾的j的数组构成公共子序列的长度，dp[i][j]值的确定有两种情况：其一当前元素的前一个元素对应相同，则说明可以构成公共子序列，其二是当前元素的前一个元素不相同，说明要比较i-1和j-2元素是否相同。
最后如果遍历到数组结束时公共子序列长度与s长度相同，说明s是t的子序列。

bool isSubsequence(string s, string t) { //动态规划，设计二维dp数组，dp[i][j]表示以i-1结尾和j-1结尾的数组的公共子序列长度int len1=s.size();int len2=t.size();vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));for(int i=1;i<=len1;++i){for(int j=1;j<=len2;++j){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1; //找到相同元素，可构成公共子序列elsedp[i][j]=dp[i][j-1]; //不相同则比较i-1与j-2元素，即dp[i][j-1]}}if(dp[len1][len2]==s.size())return true;return false;}

二、115 不同的子序列

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

核心：dp[i][j]表示以i-1结尾的s和以j-1结尾的t的不同子序列数
dp[i][j]值的确定有两种情况，其一当前元素的前一个元素对应相同，那么dp[i][j]可以是用s[i-1]来匹配（dp[i-1][j-1]），也可以是不用s[i-1]来匹配（dp[i-1][j]）；其二是当前元素的前一个元素不相同时，dp[i][j]不用s[i-1]匹配。
此外dp[i][0]和dp[0][j]以及dp[0][0]的初始化是不同的。

int numDistinct(string s, string t) {//动态规划:dp[i][j]以i-1结尾的s和以j-1结尾的t的不同子序列个数vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));//初始化，dp[i][0]和dp[0][j]的初始化不同，前者是s得到空串的个数是1，后者是空串得到t的个数是0for(int i=0;i<=s.size();++i)dp[i][0]=1;for(int j=1;j<=t.size();++j)dp[0][j]=0; //包括dp[0][0]=1for(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];elsedp[i][j]=dp[i-1][j]; }}return dp[s.size()][t.size()];}