建设银行海淀支行 网站,营销网站方案设计,宿迁房价,多php网站建设1.判断子序列#xff1a;
动态规划五部曲分析如下#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的字符串t#xff0c;相同子序列的长度为dp[i][j]。
注意这里是判断s是否…1.判断子序列
动态规划五部曲分析如下
确定dp数组dp table以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
如果t的长度小于s那直接return false如果s的长度为0是return true
有同学问了为啥要表示下标i-1为结尾的字符串呢为啥不表示下标i为结尾的字符串呢
为什么这么定义我在 718. 最长重复子数组 (opens new window)中做了详细的讲解。
其实用i来表示也可以
但我统一以下标i-1为结尾的字符串来计算这样在下面的递归公式中会容易理解一些如果还有疑惑可以继续往下看。 2.确定递推公式
在确定递推公式的时候首先要考虑如下两种操作整理如下
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];
其实这里 大家可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的区别就是 本题 如果删元素一定是字符串t而 1143.最长公共子序列 是两个字符串都可以删元素。 3.dp数组如何初始化
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]所以dp[0][0]和dp[i][0]是一定要初始化的。
这里大家已经可以发现在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
因为这样的定义在dp二维矩阵中可以留出初始化的区间如图 如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t初始化就比较麻烦了。
dp[i][0] 表示以下标i-1为结尾的字符串与空字符串的相同子序列长度所以为0. dp[0][j]同理。
vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));4.确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]那么遍历顺序也应该是从上到下从左到右
如图所示 5.举例推导dp数组
以示例一为例输入s abc, t ahbgdcdp状态转移图如下 dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明s与t的最长相同子序列就是s那么s 就是 t 的子序列。
图中dp[s.size()][t.size()] 3 而s.size() 也为3。所以s是t 的子序列返回true。
动规五部曲分析完毕C代码如下
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;else dp[i][j] dp[i][j - 1];}}if (dp[s.size()][t.size()] s.size()) return true;return false;}
}; 2.不同的子序列
这道题目如果不是子序列而是要求连续序列的那就可以考虑用KMP。
这道题的问题就是s里边删除元素变成t的方法数
动规五部曲分析如下
确定dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
为什么i-1j-1 这么定义我在 718. 最长重复子数组 (opens new window)中做了详细的讲解。 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]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]。
在判断子序列中这里是加1的那这道题为什么不加1
因为判断子序列中求的是s和t的相同子序列的长度而这道题求的是s里边删除元素变成t的方法数所以当s[i - 1] 与 t[j - 1]相等时方法数不变
一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。
这里可能有录友不明白了为什么还要考虑 不用s[i - 1]来匹配都相同了指定要匹配啊。
例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];
首先他是方法数然后dp[i][j]是以s[i-1]为结尾的s的子序列中找以j-1为结尾的tdp数组的含义其实他是由dp[i-1][j]为基础推出来的只不过是当s[i - 1] 与 t[j - 1]相等时多了一个情况就是以s[i-1]为结尾去代替dp[i-1][j]种方法中的结尾字母最后是把他们加起来相当于dp[i - 1][j - 1]是增量。
这个不相等时就相当于没有增量。
当s[i - 1] 与 t[j - 1]不相等时dp[i][j]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1][j]
所以递推公式为dp[i][j] dp[i - 1][j];
这里可能有录友还疑惑为什么只考虑 “不用s[i - 1]来匹配” 这种情况 不考虑 “不用t[j - 1]来匹配” 的情况呢。
这里大家要明确我们求的是 s 中有多少个 t而不是 求t中有多少个s所以只考虑 s中删除元素的情况即 不用s[i - 1]来匹配 的情况。 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][j]的定义不要凭感觉初始化。
dp[i][0]表示什么呢
dp[i][0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。
那么dp[i][0]一定都是1因为也就是把以i-1为结尾的s删除所有元素出现空字符串的个数也就是方法数就是1。
再来看dp[0][j]dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。
那么dp[0][j]一定都是0s如论如何也变成不了t。
最后就要看一个特殊位置了即dp[0][0] 应该是多少。
dp[0][0]应该是1空字符串s可以删除0个元素变成空字符串t。
初始化分析完毕代码如下
vectorvectorlong long dp(s.size() 1, vectorlong long(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; // 其实这行代码可以和dp数组初始化的时候放在一起但我为了凸显初始化的逻辑所以还是加上了。 4.确定遍历顺序
从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。 所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
代码如下
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];}}
}5.举例推导dp数组
以sbaeggtbag为例推导dp数组状态如下 动规五部曲分析完毕代码如下
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()];}
};
32 位的有符号整数的取值范围以及数值溢出
【C语言】uint8_t、uint16_t、uint32_t、uint64_t是什么
int的取值范围为-2^31 ---- 2^31-1 ,即-2147483648 - 2147483647
uint32_t.min0 uint32_t.max4294967295 uint64_t.min0 uint64_t.max18446744073709551615
这里用uint32_t也可以
