单位网站维护 网站建设岗位,深圳手机移动网站开发,做网站接单的网站,上海著名企业392.判断子序列 dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的字符串t#xff0c;相同子序列的长度为dp[i][j]。
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了if (s[i - 1] ! t[j - 1]) 相当于t要删除元素#xff0c;继续匹配
if (s… 392.判断子序列 dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配
if (s[i - 1] t[j - 1])那么dp[i][j] dp[i - 1][j - 1] 1;因为找到了一个相同的字符相同子序列长度自然要在dp[i-1][j-1]的基础上加1如果不理解在回看一下dp[i][j]的定义
if (s[i - 1] ! t[j - 1])此时相当于t要删除元素t如果把当前元素t[j - 1]删除那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了即dp[i][j] dp[i][j - 1];
class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorintdp(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 dp[i][j] dp[i][j - 1];}}if(dp[s.size()][t.size()] s.size()){return true;}return false;}
}; 115.不同的子序列 dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
s[i - 1] 与 t[j - 1]相等s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。
class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1));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()];}
};
