网站为什么要seo?,网站建设三剑客,优秀的设计网站有哪些内容,seo是什么意思广东话一、判断子序列
题目描述#xff1a; 思路和想法#xff1a; 这道题目还是最长公共子序列的拓展#xff0c;只是这里进行删除的一定是t字符串#xff0c;当不相等时#xff0c;dp[i][j] dp[i][j - 1]#xff1b;其余基本一致。当最长公共子序列个数等s.size()时#x…一、判断子序列
题目描述 思路和想法 这道题目还是最长公共子序列的拓展只是这里进行删除的一定是t字符串当不相等时dp[i][j] dp[i][j - 1]其余基本一致。当最长公共子序列个数等s.size()时返回true● 1143.最长公共子序列
#includestring
#includevector
using namespace std;class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() 0) return true;if(s.size() t.size()) return false;vectorvectorint dp(s.size() 1, vectorint(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{//删除元素一定是t字符串dp[i][j] dp[i][j - 1];}if(dp[i][j] s.size()) return true;}}return false;}
};
二、不同的子序列
题目描述 思路和想法
1dp[i][j] : 以i - 1为结尾的s中有j - 1为尾的t的个数。
2当s[i - 1] j[i - 1]时dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];当s[i - 1] ! j[i - 1]时,dp[i][j] dp[i - 1][j]。
这里要注意dp数组的定义
1vectorvectorint dp(s.size() 1, vectorint(t.size() 1,0));会出现溢出的情况 2 vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1,0));
#includevector
#includestring
using namespace std;class Solution {
public:int numDistinct(string s, string t) {if(s.size() t.size()) return 0;vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1,0));//第一行和第一列初始化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()]; }
};
