二级网站模板,jquery网站模板下载,南宁模板建站多少钱,苏州网站开发建设制作目录 动态规划_两个数组的 dp #xff08;含字符串数组#xff09;
1. 最⻓公共⼦序列#xff08;medium#xff09;
解析#xff1a;
1. 状态表⽰#xff1a;
2. 状态转移⽅程#xff1a;
3. 初始化#xff1a;编辑
4. 填表顺序#xff1a;编辑
5. 返回值…目录 动态规划_两个数组的 dp 含字符串数组
1. 最⻓公共⼦序列medium
解析
1. 状态表⽰
2. 状态转移⽅程
3. 初始化编辑
4. 填表顺序编辑
5. 返回值
代码编写
总结
2. 不相交的线medium
解析
代码编写
总结
3. 不同的⼦序列hard
解析
1. 状态表⽰
2. 状态转移⽅程编辑
3. 初始化编辑
4. 填表顺序
5. 返回值编辑
总结
4. 通配符匹配hard
解析
1. 状态表⽰
2. 状态转移⽅程编辑
3. 初始化编辑
4. 填表顺序编辑
5. 返回值
代码编写
总结
5. 正则表达式匹配hard
解释
1. 状态表⽰编辑
2. 状态转移⽅程编辑
3. 初始化编辑
4. 填表顺序
5. 返回值
代码编写
总结
6. 交错字符串medium
解析
1. 状态表⽰编辑
2. 状态转移⽅程编辑
3. 初始化编辑
4. 填表顺序
5. 返回值
代码编写
总结
7. 两个字符串的最⼩ ASCII 删除和medium
解析
1. 状态表⽰编辑
2. 状态转移⽅程
3. 初始化
4. 填表顺序
5. 返回值编辑
代码编写
总结
8. 最⻓重复⼦数组medium
解析
1. 状态表⽰编辑
2. 状态转移⽅程编辑
3. 初始化
4. 填表顺序
5. 返回值
代码编写
总结
总结不易~本章节对我的收获很大希望对你也是~ 动态规划_两个数组的 dp 含字符串数组
经过前面一系列动态规划的学习我相信对这一部分已经有了充分较为完整的理解接下来是对两个数组的 dp 含字符串数组分支的继续学习~ 1. 最⻓公共⼦序列medium
求两个子串的最长公共子序列的长度 解析
1. 状态表⽰ 对于两个数组的动态规划我们的定义状态表⽰的经验就是 i. 选取第⼀个数组 [0, i] 区间以及第⼆个数组 [0, j] 区间作为研究对象 ii. 结合题⽬要求定义状态表⽰。 在这道题中我们根据定义状态表⽰为 dp[i][j] 表⽰ s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的⼦序列中最⻓公共⼦序列的⻓度。 2. 状态转移⽅程 分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况分情况讨论。 对于 dp[i][j] 我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论 i. 两个字符相同 s1[i] s2[j] 那么最⻓公共⼦序列就在 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间上找到⼀个最⻓的然后再加上 s1[i] 即可。因此dp[i][j] dp[i - 1][j - 1] 1 ii. 两个字符不相同 s1[i] ! s2[j] 那么最⻓公共⼦序列⼀定不会同时以 s1[i]和 s2[j] 结尾。那么我们找最⻓公共⼦序列时有下⾯三种策略 • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找此时最⼤⻓度为 dp[i - 1][j] • 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找此时最⼤⻓度为 dp[i ][j - 1] • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找此时最⼤⻓度为 dp[i - 1][j - 1] 。 我们要三者的最⼤值即可。但是我们细细观察会发现第三种包含在第⼀种和第⼆种情况⾥ ⾯但是我们求的是最⼤值并不影响最终结果。因此只需求前两种情况下的最⼤值即可。 综上状态转移⽅程为 if(s1[i] s2[j]) dp[i][j] dp[i - 1][j - 1] 1 ; if(s1[i] ! s2[j]) dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) 。 3. 初始化 a. 「空串」是有研究意义的因此我们将原始 dp 表的规模多加上⼀⾏和⼀列表⽰空串。 b. 引⼊空串后⼤⼤的⽅便我们的初始化。 c. 但也要注意「下标的映射关系」以及⾥⾯的值要「保证后续填表是正确的」。 当 s1 为空时没有⻓度同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证 后续填表是正确的。 4. 填表顺序 根据「状态转移⽅程」得从上往下填写每⼀⾏每⼀⾏从左往右。 5. 返回值 根据「状态表⽰」得返回 dp[m][n] 。 代码编写
class Solution {
public:int longestCommonSubsequence(string s1, string s2) {int ns1.size(),ms2.size();s1 s1;s2 s2;vectorvectorint dp(n1,vectorint(m1));int ret0;for(int i1;in;i){for(int j1;jm;j){if(s1[i]s2[j])dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}return dp[n][m];}
};
总结 对于两个数组dp问题通过这一道模板题就有很好的理解最重要的还是定义状态转移方程熟悉这一题的套路就是求出两个字符串的最长公共子序列的长度是通过s1[0,i] 和 s2[0,j]这两个子串的范围来获得的在一个二维dp内能够进行表示~ 2. 不相交的线medium
求两个数组的最长公共子序列的长度 解析
开始第一眼看这一题的时候就是要求不相交的线的个数一下子就被难到了要求不相交线的个数那用双指针呢然后分别遍历两个数组只要满足不回退就不会相交但是这样就不能确定遍历一遍后得到的线的个数是否是最多的
但是又仔细一看这要需要被点一下只需要你仔细观察一下是不是就也是在两个数组内求最长的公共子序列问题那么就简单了只需要跟上一题一样分析就好啦~ 如果要保证两条直线不相交那么我们「下⼀个连线」必须在「上⼀个连线」对应的两个元素的 「后⾯」寻找相同的元素。这不就转化成「最⻓公共⼦序列」的模型了嘛。那就是在这两个数组中 寻找「最⻓的公共⼦序列」。 只不过是在整数数组中做⼀次「最⻓的公共⼦序列」代码⼏乎⼀模⼀样这⾥就不再赘述算法原理啦~ 代码编写
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {//最长公共子序列int nnums1.size(),mnums2.size();vectorvectorint dp(n1,vectorint(m1));for(int i1;in;i){for(int j1;jm;j){if(nums1[i-1]nums2[j-1]) dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}return dp[n][m];}
};
总结 需要仔细观察满足哪种条件不能硬着头就开始暴力一定有更优解的办法~ 3. 不同的⼦序列hard
求字符串s内包含多少个字符串t 解析
1. 状态表⽰ 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下 i. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象结合题⽬的要求来定义「状态表⽰」 ii. 然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移⽅程」。 我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。 dp[i][j] 表⽰在字符串 s 的 [0, j] 区间内的所有⼦序列中有多少个 t 字符串 [0,i] 区间内的⼦串。 2. 状态转移⽅程 ⽼规矩根据「最后⼀个位置」的元素结合题⽬要求分情况讨论 i. 当 t[i] s[j] 的时候此时的⼦序列有两种选择 • ⼀种选择是⼦序列选择 s[j] 作为结尾此时相当于在状态 dp[i - 1][j - 1] 中的所有符合要求的⼦序列的后⾯再加上⼀个字符 s[j] 请⼤家结合状态表⽰好好理解这句话此时 dp[i][j] dp[i - 1][j - 1] • 另⼀种选择是我就是任性我就不选择 s[j] 作为结尾。此时相当于选择了状态dp[i][j - 1] 中所有符合要求的⼦序列。我们也可以理解为继承了上个状态⾥⾯的求得的⼦序列。此时 dp[i][j] dp[i][j - 1] 两种情况加起来就是 t[i] s[j] 时的结果。 ii. 当 t[i] ! s[j] 的时候此时的⼦序列只能从 dp[i][j - 1] 中选择所有符合要求的⼦序列。只能继承上个状态⾥⾯求得的⼦序列 dp[i][j] dp[i][j - 1] 综上所述状态转移⽅程为 ▪ 所有情况下都可以继承上⼀次的结果 dp[i][j] dp[i][j - 1] ▪ 当 t[i] s[j] 时可以多选择⼀种情况 dp[i][j] dp[i - 1][j - 1] 3. 初始化 a. 「空串」是有研究意义的因此我们将原始 dp 表的规模多加上⼀⾏和⼀列表⽰空串。 b. 引⼊空串后⼤⼤的⽅便我们的初始化。 c. 但也要注意「下标的映射关系」以及⾥⾯的值要「保证后续填表是正确的」。 当 s 为空时 t 的⼦串中有⼀个空串和它⼀样因此初始化第⼀⾏全部为 1 。 4. 填表顺序 「从上往下」填每⼀⾏每⼀⾏「从左往右」。 5. 返回值 根据「状态表⽰」返回 dp[m][n] 的值。 本题有⼀个巨恶⼼的地⽅题⽬上说结果不会超过 int 的最⼤值但是实际在计算过程会会超。为 了避免报错我们选择 double 存储结果 class Solution {
public:int numDistinct(string s, string t) {int nt.size(),ms.size();vectorvectordouble dp(n1,vectordouble(m1));for(int i0;im;i)dp[0][i]1;for(int i1;in;i){for(int j1;jm;j){if(t[i-1]s[j-1]) dp[i][j]dp[i-1][j-1];dp[i][j]dp[i][j-1];}}return dp[n][m];}
}; 总结 虽然是困难题但是还是离不开我们上一题的思路就是对两个字符串的结尾字符考虑是否存在的问题~ 4. 通配符匹配hard
题目有点难理解*可以单独存在去匹配任意一个或者多个字符可以匹配任何一个字符求p是否可以完全匹配s 解析
1. 状态表⽰ 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下 i. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象结 合题⽬的要求来定义「状态表⽰」 ii. 然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移 ⽅程」。 我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。 因此我们定义状态表⽰为 dp[i][j] 表⽰ p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串。 2. 状态转移⽅程 ⽼规矩根据最后⼀个位置的元素结合题⽬要求分情况讨论 i. 当 s[i] p[j] 或 p[j] ? 的时候此时两个字符串匹配上了当前的⼀个字 符只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个 状态中的匹配结果 dp[i][j] dp[i][j - 1] ii. 当 p[j] * 的时候此时匹配策略有两种选择 • ⼀种选择是 * 匹配空字符串此时相当于它匹配了⼀个寂寞直接继承状态 dp[i][j - 1] 此时 dp[i][j] dp[i][j - 1] • 另⼀种选择是 * 向前匹配 1 ~ n 个字符直⾄匹配上整个 s1 串。此时相当于 从 dp[k][j - 1] (0 k i) 中所有匹配情况中选择性继承可以成功的 情况。此时 dp[i][j] dp[k][j - 1] (0 k i) iii. 当 p[j] 不是特殊字符且不与 s[i] 相等时⽆法匹配。 三种情况加起来就是所有可能的匹配结果。 综上所述状态转移⽅程为 ▪ 当 s[i] p[j] 或 p[j] ? 时 dp[i][j] dp[i][j - 1] ▪ 当 p[j] * 时有多种情况需要讨论 dp[i][j] dp[k][j - 1] (0 k i) 优化当我们发现计算⼀个状态的时候需要⼀个循环才能搞定的时候我们要想到去优化。优 化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来然后⽤数学的⽅式 做⼀下等价替换 当 p[j] * 时状态转移⽅程为 dp[i][j] dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] ...... 我们发现 i 是有规律的减⼩的因此我们去看看 dp[i - 1][j] dp[i - 1][j] dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3] [j - 1] ...... 我们惊奇的发现 dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外其余的都可以⽤ dp[i - 1][j] 替代。因此我们优化我们的状态转移⽅程为 dp[i][j] dp[i - 1][j] || dp[i][j - 1] 。 3. 初始化 由于 dp 数组的值设置为是否匹配为了不与答案值混淆我们需要将整个数组初始化为 false 。 由于需要⽤到前⼀⾏和前⼀列的状态我们初始化第⼀⾏、第⼀列即可。 ◦ dp[0][0] 表⽰两个空串能否匹配答案是显然的 初始化为 true 。 ◦ 第⼀⾏表⽰ s 是⼀个空串 p 串和空串只有⼀种匹配可能即 p 串表⽰为 *** 此时 也相当于空串匹配上空串。所以我们可以遍历 p 串把所有前导为 * 的 p ⼦串和空串 的 dp 值设为 true 。 ◦ 第⼀列表⽰ p 是⼀个空串不可能匹配上 s 串跟随数组初始化即可。 4. 填表顺序 从上往下填每⼀⾏每⼀⾏从左往右。 5. 返回值 根据状态表⽰返回 dp[m][n] 的值 代码编写
class Solution {
public:bool isMatch(string s, string p) {int ns.size(),mp.size();vectorvectorbool dp(n1,vectorbool(m1));s s,p p;dp[0][0]true;for(int i1;im;i){if(p[i]*) dp[0][i]true;else break;}for(int i1;in;i){for(int j1;jm;j){if(p[j]*){dp[i][j]dp[i][j-1]||dp[i-1][j];}else{if(p[j]?||s[i]p[j])dp[i][j]dp[i-1][j-1];}}}return dp[n][m];}
};
总结 这一题是真正的难题还需要多加练习考虑为什么要采用dp[i][j] 表⽰ p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串。 这种状态表达也就是经验题目要求 5. 正则表达式匹配hard
这是一道真正的难题题目跟上一题意思大差不差就是这个*不能单独出现必须要配上前面一个字符那么只要配上前面一个字符就可以进行匹配空串但是只要出现连续两个字符不是*那么就不能匹配空串 解释
1. 状态表⽰ 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下 i. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象结合题⽬的要求来定义「状态表⽰」 ii. 然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移 ⽅程」。 我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。 因此我们定义状态表⽰ dp[i][j] 表⽰字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配。 2. 状态转移⽅程 ⽼规矩根据最后⼀个位置的元素结合题⽬要求分情况讨论 a. 当 s[i] p[j] 或 p[j] . 的时候此时两个字符串匹配上了当前的⼀个字符只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果 dp[i][j] dp[i - 1][j - 1] b. 当 p[j] * 的时候和上道题稍有不同的是上道题 * 本⾝便可匹配 0 ~ n 个 字符但此题是要带着 p[j - 1] 的字符⼀起匹配 0 ~ n 个和 p[j - 1] 相同的字符。此时匹配策略 有两种选择 ▪ ⼀种选择是 p[j - 1]* 匹配空字符串此时相当于这两个字符都匹配了⼀个寂寞直接继承状态 dp[i][j - 2] 此时 dp[i][j] dp[i][j - 2] ▪ 另⼀种选择是 p[j - 1]* 向前匹配 1 ~ n 个字符直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 2] (0 k i) 中所有匹配情况中选择性继承可以成功的情况。此时 dp[i][j] dp[k][j - 2] (0 k i 且 s[k]~s[i] p[j- 1]) c. 当 p[j] 不是特殊字符且不与 s[i] 相等时⽆法匹配。 三种情况加起来就是所有可能的匹配结果。 综上所述状态转移⽅程为 ▪ 当 s[i] p[j] 或 p[j] . 时 dp[i][j] dp[i][j - 1] ▪ 当 p[j] * 时有多种情况需要讨论 dp[i][j] dp[i][j - 2] dp[i][j] dp[k][j - 1] (0 k i) 。 优化当我们发现计算⼀个状态的时候需要⼀个循环才能搞定的时候我们要想到去优化。优 化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来然后⽤数学的⽅式 做⼀下等价替换 当 p[j] * 时状态转移⽅程为 dp[i][j] dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 2][j - 2] ...... 我们发现 i 是有规律的减⼩的因此我们去看看 dp[i - 1][j] dp[i - 1][j] dp[i - 1][j - 2] || dp[i - 2][j - 2] || dp[i - 3][j - 2] ...... 我们惊奇的发现 dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外其余的都可以⽤ dp[i - 1][j] 替代。因此我们优化我们的状态转移⽅程为 dp[i][j] dp[i][j - 2] || dp[i - 1][j] 。 3. 初始化 由于 dp 数组的值设置为是否匹配为了不与答案值混淆我们需要将整个数组初始化为false 。 由于需要⽤到前⼀⾏和前⼀列的状态我们初始化第⼀⾏、第⼀列即可。 dp[0][0] 表⽰两个空串能否匹配答案是显然的 初始化为 true 。 第⼀⾏表⽰ s 是⼀个空串 p 串和空串只有⼀种匹配可能即 p 串全部字符表⽰为 任⼀字符 *此时也相当于空串匹配上空串。所以我们可以遍历 p 串把所有前导为 任⼀字符 * 的 p ⼦串和空串的 dp 值设为 true 。 第⼀列表⽰ p 是⼀个空串不可能匹配上 s 串跟随数组初始化即可。 4. 填表顺序 从上往下填每⼀⾏每⼀⾏从左往右。 5. 返回值 根据状态表⽰返回 dp[m][n] 的值。 代码编写
class Solution {
public:bool isMatch(string s, string p) {int n s.size(),m p.size();vectorvectorint dp(n1,vectorint(m1));p p, s s;dp[0][0]true;for(int i2;im;i2){if(p[i] *) dp[0][i]1;else break;}for(int i1;in;i){for(int j1;jm;j){if(p[j]*) dp[i][j]dp[i][j-2] || (p[j-1] . || p[j-1]s[i]) dp[i-1][j];else dp[i][j] (s[i] p[j] || p[j] .) dp[i-1][j-1];}}return dp[n][m];}
};
总结 这一题真的有难度对于最重要的状态表达式描述好后状态转移方程和初始化 就是细节问题~对于这一题的状态转移方程会很麻烦所以一定要话清楚草图和考虑每一个字符前面一个字符出现的各种情况但是讨论完发现其实也就是两行代码这一题值得多总结多思考~ 6. 交错字符串medium
给定两个字符串s1,s2,来判断是否可以交错形成字符串s3 解析 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下 i. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象结合题⽬的要求来定义「状态表⽰」 ii. 然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移⽅程」。 我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。 这道题⾥⾯空串是有研究意义的因此我们先预处理⼀下原始字符串前⾯统⼀加上⼀个占位符 s1 s1, s2 s2, s3 s3 。 1. 状态表⽰ dp[i][j] 表⽰字符串 s1 中 [1, i] 区间内的字符串以及 s2 中 [1, j] 区间内的字符串能否拼接成 s3 中 [1, i j] 区间内的字符串。 2. 状态转移⽅程 先分析⼀下题⽬题⽬中交错后的字符串为 s1 t1 s2 t2 s3 t3...... 看似⼀个 s ⼀个 t 。实际上 s1 能够拆分成更⼩的⼀个字符进⽽可以细化成 s1 s2 s3 t1 t2 s4...... 。 也就是说并不是前⼀个⽤了 s 的⼦串后⼀个必须要⽤ t 的⼦串。这⼀点理解对我们的状 态转移很重要。 继续根据两个区间上「最后⼀个位置的字符」结合题⽬的要求来进⾏「分类讨论」 i. 当 s3[i j] s1[i] 的时候说明交错后的字符串的最后⼀个字符和 s1 的最后⼀个字符匹配了。那么整个字符串能否交错组成变成 s1 中 [1, i - 1] 区间上的字符串以及 s2 中 [1, j] 区间上的字符串能够交错形成 s3 中 [1, i j - 1] 区间上的字符串也就是 dp[i - 1][j] 此时 dp[i][j] dp[i - 1][j] ii. 当 s3[i j] s2[j] 的时候说明交错后的字符串的最后⼀个字符和 s2 的最后⼀个字符匹配了。那么整个字符串能否交错组成变成 s1 中 [1, i] 区间上的字符串以及 s2 中 [1, j - 1] 区间上的字符串能够交错形成 s3 中 [1, i j - 1] 区间上的字符串也就是 dp[i][j - 1] iii. 当两者的末尾都不等于 s3 最后⼀个位置的字符时说明不可能是两者的交错字符串。 上述三种情况下只要有⼀个情况下能够交错组成⽬标串就可以返回 true 。因此我们可以 定义状态转移为 dp[i][j] (s1[i - 1] s3[i j - 1] dp[i - 1][j]) || (s2[j - 1] s3[i j - 1] dp[i][j - 1]) 只要有⼀个成⽴结果就是 true 。 3. 初始化 由于⽤到 i - 1 , j - 1 位置的值因此需要初始化「第⼀个位置」以及「第⼀⾏」和「第⼀列」。 ◦ 第⼀个位置 dp[0][0] true 因为空串 空串能够构成⼀个空串。 ◦ 第⼀⾏ 第⼀⾏表⽰ s1 是⼀个空串我们只⽤考虑 s2 即可。因此状态转移之和 s2 有关 dp[0][j] s2[j - 1] s3[j - 1] dp[0][j - 1] j 从 1 到 n n 为 s2 的⻓度 ◦ 第⼀列 第⼀列表⽰ s2 是⼀个空串我们只⽤考虑 s1 即可。因此状态转移之和 s1 有关 dp[i][0] s1[i - 1] s3[i - 1] dp[i - 1][0] i 从 1 到 m m 为 s1 的⻓度 4. 填表顺序 根据「状态转移」我们需要「从上往下」填每⼀⾏每⼀⾏「从左往右」。 5. 返回值 根据「状态表⽰」我们需要返回 dp[m][n] 的值。 代码编写
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n s1.size(), m s2.size();if (m n ! s3.size())return false;vectorvectorint dp(n 1, vectorint(m 1));s1 s1;s2 s2;s3 s3;dp[0][0] 1;for (int i 1; i m; i) {if (s2[i] s3[i])dp[0][i] 1;elsebreak;}for (int i 1; i n; i) {if (s1[i] s3[i])dp[i][0] 1;elsebreak;}for (int i 1; i n; i) {for (int j 1; j m; j) {dp[i][j] (s1[i] s3[i j]) dp[i - 1][j] ||(s2[j] s3[i j]) dp[i][j - 1];}}return dp[n][m];}
};
总结 有了上面两题的试炼这题简直小ks就只需要考虑清楚状态转移方程是在 || 下进行的就是不要连续用if else 进行判断再就是初始化这个细节问题分别考虑s1,s2空串的情况进行初始化填表 7. 两个字符串的最⼩ ASCII 删除和medium
这一题要我们求出删除最小的字符的ASCII值让两个字符串相等 解析 正难则反求两个字符串的最⼩ ASCII 删除和其实就是找到两个字符串中所有的公共⼦序列⾥⾯ ASCII 最⼤和。 因此我们的思路就是按照「最⻓公共⼦序列」的分析⽅式来分析。 1. 状态表⽰ dp[i][j] 表⽰ s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的⼦序列中公共⼦序列的 ASCII 最⼤和。 2. 状态转移⽅程 对于 dp[i][j] 根据「最后⼀个位置」的元素结合题⽬要求分情况讨论 i. 当 s1[i] s2[j] 时应该先在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内找⼀个公共⼦序列的最⼤和然后在它们后⾯加上⼀个 s1[i] 字符即可。 此时 dp[i][j] dp[i - 1][j - 1] s1[i] ii. 当 s1[i] ! s2[j] 时公共⼦序列的最⼤和会有三种可能 • s1 的 [0, i - 1] 区间以及 s2 的 [0, j] 区间内此时 dp[i][j] dp[i - 1][j] • s1 的 [0, i] 区间以及 s2 的 [0, j - 1] 区间内此时 dp[i][j] dp[i][j - 1] • s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内此时 dp[i][j] dp[i - 1][j - 1] 。 但是前两种情况⾥⾯包含了第三种情况因此仅需考虑前两种情况下的最⼤值即可。 综上所述状态转移⽅程为 ◦ 当 s1[i - 1] s2[j - 1] 时 dp[i][j] dp[i - 1][j - 1] s1[i] ◦ 当 s1[i - 1] ! s2[j - 1] 时 dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) 3. 初始化 a. 「空串」是有研究意义的因此我们将原始 dp 表的规模多加上⼀⾏和⼀列表⽰空串。 b. 引⼊空串后⼤⼤的「⽅便我们的初始化」。 c. 但也要注意「下标的映射」关系以及⾥⾯的值要保证「后续填表是正确的」。 当 s1 为空时没有⻓度同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证 后续填表是正确的。 4. 填表顺序 「从上往下」填每⼀⾏每⼀⾏「从左往右」。 5. 返回值 根据「状态表⽰」我们不能直接返回 dp 表⾥⾯的某个值 i. 先找到 dp[m][n] 也是最⼤公共 ASCII 和 ii. 统计两个字符串的 ASCII 码和 s u m iii. 返回 sum - 2 * dp[m][n] 代码编写
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int ns1.size(),ms2.size();s1 s1,s2 s2;int ret0;for(int i1;in;i) ret(s1[i]);for(int i1;im;i) ret(s2[i]);vectorvectorint dp(n1,vectorint(m1));for(int i1;in;i){for(int j1;jm;j){if(s1[i]s2[j]) dp[i][j] dp[i-1][j-1](s2[j]);else dp[i][j]max(dp[i][j],max(dp[i][j-1],dp[i-1][j]));}}ret-2*dp[n][m];return ret;}
};
总结 这一题要我们求出删除最小的字符的ASCII值让两个字符串相等如果真的顺着题目往下想还真的挺难要考虑的情况好多但是但凡反着思考一下我们只要求出最大的公共子序列ASCII值就能直到最小值并且我们前面也做过一样的求最大公共子序列的问题所以还是很轻松的~ 8. 最⻓重复⼦数组medium
求出两个子数组中最长公共子数组的长度 解析 ⼦数组是数组中「连续」的⼀段我们习惯上「以某⼀个位置为结尾」来研究。由于是两个数组 因此我们可以尝试以第⼀个数组的 i 位置为结尾以及第⼆个数组的 j 位置为结尾来解决问题。 1. 状态表⽰ dp[i][j] 表⽰「以第⼀个数组的 i 位置为结尾」以及「第⼆个数组的 j 位置为结尾」公共的 、⻓度最⻓的「⼦数组」的⻓度。 2. 状态转移⽅程 对于 dp[i][j] 当 nums1[i] nums2[j] 的时候才有意义此时最⻓重复⼦数组的 ⻓度应该等于 1 加上除去最后⼀个位置时以 i - 1, j - 1 为结尾的最⻓重复⼦数组的⻓ 度。 因此状态转移⽅程为 dp[i][j] 1 dp[i - 1][j - 1] 3. 初始化 为了处理「越界」的情况我们可以添加⼀⾏和⼀列 dp 数组的下标从 1 开始这样就⽆需初 始化。 第⼀⾏表⽰第⼀个数组为空此时没有重复⼦数组因此⾥⾯的值设置成 0 即可 第⼀列也是同理。 4. 填表顺序 根据「状态转移」我们需要「从上往下」填每⼀⾏每⼀⾏「从左往右」。 5. 返回值 根据「状态表⽰」我们需要返回 dp 表⾥⾯的「最⼤值」。 代码编写
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int n nums1.size(), m nums2.size();vectorvectorint dp(n1,vectorint(m1));int ret0;for(int i1;in;i){for(int j1;jm;j){if(nums1[i-1]nums2[j-1]) dp[i][j] dp[i-1][j-1] 1;retmax(ret,dp[i][j]);}}return ret;}
};
总结 有过前面子数组和子序列的总结我觉得我自身是得到了质的飞跃~现在再看这种题也已是题中人了嘿嘿嘿加油 总结不易~本章节对我的收获很大希望对你也是~
