网站建设与网页设计论述题,wordpress开户多站点,wordpress js 太多,常用的网站开发392.判断子序列 思路#xff1a;判断子序列的问题#xff0c;其实与最大公共子序列的问题是一样的#xff0c;所以基本上写出来是一样的#xff0c;但是今天又犯了一个错误#xff0c;对于非连续子序列#xff0c;不仅要在相等的时候进行更新#xff0c;而且不等的时候也…392.判断子序列 思路判断子序列的问题其实与最大公共子序列的问题是一样的所以基本上写出来是一样的但是今天又犯了一个错误对于非连续子序列不仅要在相等的时候进行更新而且不等的时候也要更新 class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size()1,vectorint(t.size()1,0));int result0;for(int i1;is.size();i){for(int j1;jt.size();j){if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]1;coutdp:dp[i][j]endl;} else{dp[i][j]dp[i][j-1];}if(dp[i][j]result)resultdp[i][j];}}coutresultendl;if(results.size())return true;return false;}
};115.不同的子序列 思路首先分析题意我们要t中找到s的最多次数而且可以非连续如果是连续的话就是KMP算法了。非连续的问题就意味着我们要t进行删除一位那么这个删除的过程是怎么样的呢这个就要讨论递推公式了遍历到t和s的最后一个位置是相等的那么此时dp[i][j]dp[i-1][j-1]但是如果此时最后一个位置不相等呢即不用t的最后一个元素去匹配故dp[i][j]dp[i-1][j]故其是分为了两种情况另外一种情况就是不相等了那么只能用前一个位置了。初始化的问题当t字符串为空的时候s字符串有东西的话都不可能匹配上则为0但是t字符串不为空s字符串为空的时候则为1如果t和s的字符串都为空那么这个时候必然为1 class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size()1,vectoruint64_t(t.size()1,0));for(int i0;is.size();i)dp[i][0]1;for(int j1;jt.size();j)dp[0][j]0;for(int i1;is.size();i){for(int j1;jt.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()];}
};
