网站建设功能需求文档,知名企业有哪些,wordpress教育相关的模板,有没有接单做加工的网站目录
392.判断子序列
思路
算法实现
115.不同的子序列
思路 算法实现
总结 392.判断子序列 题目链接 文章链接 思路 利用动规五部曲进行分析#xff1a;
1.确定dp数组及其下标含义#xff1a; dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的…目录
392.判断子序列
思路
算法实现
115.不同的子序列
思路 算法实现
总结 392.判断子序列 题目链接 文章链接 思路 利用动规五部曲进行分析
1.确定dp数组及其下标含义 dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
2.确定递推公式 主要考虑两种情况
当s[i - 1] t[j - 1]时t中找到了一个字符在s中也出现了当s[i - 1] ! t[j - 1]时相当于t要删除元素继续匹配。 对于第一种情况dp[i][j] dp[i - 1][j - 1] 1因为找到了一个相同的字符相同子序列长度自然要在dp[i-1][j-1]的基础上加1 对于第二种情况此时相当于t要删除元素t如果把当前元素t[j - 1]删除那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了即dp[i][j] dp[i][j - 1]
3.dp数组初始化 又由递推公式可知dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]所以dp[0][j]和dp[i][0]是一定要初始化的。 因为在定义dp数组时就是以下标i - 1和j - 1为结尾因此当i 0和j 0时都是本身没有意义的其他下标的初值对结果没有影响为了方便可以都初始化为0
4.确定遍历顺序 从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]那么遍历顺序也应该是从上到下从左到右如图所示 5.打印dp数组 以示例一为例输入s abc, t ahbgdcdp状态转移图如下 算法实现
class Solution {
public:bool isSubsequence(string s, string t) {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;elsedp[i][j] dp[i][j - 1];}}if (dp[s.size()][t.size()] s.size()) return true;return false;}
};
115.不同的子序列 题目链接 文章链接 思路 利用动规五部曲进行分析
1.确定dp数组及其下标的含义 dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.确定递推公式 也是分两种情况
s[i - 1]与t[j - 1]相等s[i - 1]与t[j - 1]不相等 当s[i - 1]与t[j - 1]相等时dp[i][j]由两部分组成第一种是单独看当前s[i - 1]与t[j - 1]的匹配那么个数为dp[i - 1][j - 1]另一部分是不论当前是否相等前面的字符匹配到t[j]传递下来的基项个数为dp[i - 1][j]; 当s[i - 1]与t[j - 1]不相等时dp[i][j]只由一部分组成就是前面的基项dp[i - 1][j]
3.初始化dp数组 从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来如图那么 dp[i][0] 和dp[0][j]是一定要初始化的。 dp[i][0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。 当s中的所有元素删除即为空字符串有且仅有唯一情况因此dp[i][0]初始化为1 再来看dp[0][j]dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。 那么dp[0][j]一定都是0s如论如何也变成不了t。 特殊位置dp[0][0]应该按照dp[i][0]的思路来空字符串s可以删除0个元素变成空字符串t因此赋值为1
4.确定遍历顺序 从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。 5.打印dp数组 以sbaeggtbag为例推导dp数组状态如下 算法实现
class Solution {
public:int numDistinct(string s, string t) {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];elsedp[i][j] dp[i - 1][j];}}return dp[s.size()][t.size()];}
};
总结 今天练习的两道题目依然是子序列问题一样的处理方法简化dp数组初始化但是在具体实现上还是比较困难的第一次尝试没有什么思路。
