网站设计主题选择,佛山茶叶网站建设,电子商城网站开发合同,做app网站设计目录
题目一——1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09;
题目二——1035. 不相交的线 - 力扣#xff08;LeetCode#xff09; 题目三——115. 不同的子序列 - 力扣#xff08;LeetCode#xff09;
题目四—— 44. 通配符匹配 - 力扣#xff08;…目录
题目一——1143. 最长公共子序列 - 力扣LeetCode
题目二——1035. 不相交的线 - 力扣LeetCode 题目三——115. 不同的子序列 - 力扣LeetCode
题目四—— 44. 通配符匹配 - 力扣LeetCode
题目五——10. 正则表达式匹配 - 力扣LeetCode
题目六——97. 交错字符串 - 力扣LeetCode
题目七——712. 两个字符串的最小ASCII删除和 - 力扣LeetCode
题目八——718. 最长重复子数组 - 力扣LeetCode 题目一——1143. 最长公共子序列 - 力扣LeetCode 这题是经典中的经典 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.初始化 我们知道状态转移方程会使用dp[i - 1][j - 1]那对于i0和j0的情况那这个dp[i - 1][j - 1]不是会越界吗为了防止这个情况的发生我们可以将dp表多开一行一列但是这样子会影响到和原数组的下标映射关系所以我们可以在原字符串前加一个空字符这样子就不会有下标映射的困扰了 此外当s1为空时没有长度同理s2也是。因此dp表里面第一行和第一列里面的值初始化为0即可保证后续填表是正确的。
a. 「空串」是有研究意义的因此我们将原始dp表的规模多加上一行和一列表示空串。b. 引入空串后大大的方便我们的初始化。c. 但也要注意「下标的映射关系」以及里面的值要「保证后续填表是正确的」。 4.填表顺序 根据「状态转移方程」得从上往下填写每一行每一行从左往右。 5.返回值 根据「状态表示」得返回dp[m][n]。 代码如下
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int mtext1.size(),ntext2.size();vectorvectorintdp(m1,vectorint(n1,0));text1 text1;text2 text2;int ret0;for(int i1;im;i){for(int j1;jn;j){if(text1[i]text2[j]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}retmax(ret,dp[i][j]);}}return ret;}
}; 题目二——1035. 不相交的线 - 力扣LeetCode 如果要保证两条直线不相交那么我们「下⼀个连线」必须在「上⼀个连线」对应的两个元素的 「后⾯」寻找相同的元素。这不就转化成「最⻓公共⼦序列」的模型了嘛。
那就是在这两个数组中 寻找「最⻓的公共⼦序列」。 只不过是在整数数组中做⼀次「最⻓的公共⼦序列」代码⼏乎⼀模⼀样这⾥就不再赘述算法原理啦~ class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {int mnums1.size(),nnums2.size();vectorvectorintdp(m1,vectorint(n1,0));int ret0;for(int i1;im;i){for(int j1;jn;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]);}retmax(ret,dp[i][j]);}}return ret;}
}; 题目三——115. 不同的子序列 - 力扣LeetCode 1.状态表示 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下
i. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的[0, j] 区间当成研究对象结合题⽬的要求来定义「状态表⽰」 ii. 然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移 ⽅程」。
我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。
dp[i][j] 表⽰在字符串 s 的 [0, j] 区间内的所有子序列中有多少个 t字符串 的 [0, i] 区间的子序列。 2.状态转移方程 接下来我们根据两个区间上“最后一个位置的字符”来进行分类讨论以确定状态转移方程。 当 t[i] s[j] 时此时的子序列有两种选择 一种选择是选择s[i]为结尾这意味着问题就是在字符串 s 的 [0, j] 区间内的所有子序列中有多少个 t字符串 的 [0, i] 区间的子序列。这意味着在 dp[i - 1][j - 1] 中的所有符合要求的子序列的后面再加上一个字符 s[j]。因此dp[i][j] dp[i - 1][j - 1]。 另一种选择是不选择s[i]为结尾这意味着问题就是在字符串 s 的 [0, j-1] 区间内的所有子序列中有多少个 t字符串 的 [0, i] 区间的子序列。这意味着我们直接继承了 dp[i][j - 1] 中所有符合要求的子序列。因此dp[i][j] dp[i][j - 1]。 综合两种情况当 t[i] s[j] 时dp[i][j] dp[i - 1][j - 1] dp[i][j - 1]。 当 t[i] ! s[j] 时由于 s[j] 与 t[i] 不匹配此时的子序列只能从 dp[i][j - 1] 中选择所有符合要求的子序列。也就是说我们只能继承上一个状态中求得的子序列。因此dp[i][j] dp[i][j - 1]。
综上所述状态转移方程可以总结为
在所有情况下dp[i][j] 都可以继承上一次的结果即 dp[i][j] dp[i][j - 1]。当 t[i] s[j] 时除了继承上一次的结果外还可以多选择一种情况即 dp[i][j] dp[i - 1][j - 1]。 3.初始化 我们知道状态转移方程会出现j-1或者i-1那当j0或者i0的时候那不是会越界吗这可不行所以我们需要另外开一行一列这样子就能防止越界情况的发生了。
只不过这样子的新dp表的下标和原数组的下标是对不上的。是需要经过-1才能得到原数组的下标的。为了避免这种麻烦我们直接给两个字符串的最前面加上一个空字符串 这样就可以免去下标映射的痛苦。
此外当 s 为空时 t 的⼦串中有⼀个空串和它⼀样因此初始化第⼀⾏全部为 1 。 4.填表顺序 我们看状态转移方程 dp[i][j] dp[i - 1][j - 1]。
这就决定了dp[i - 1][j - 1]一定比dp[i][j]先出现所以是从左往右从上往下。 5.返回值 dp[i][j] 表⽰在字符串 s 的 [0, j] 区间内的所有子序列中有多少个 t字符串 的 [0, i] 区间的子序列。
所以我们返回dp[t.size()][s.size()]。即可 本题有⼀个巨恶⼼的地⽅题⽬上说结果不会超过 int 的最⼤值但是实际在计算过程会会超。为了避免报错我们选择 double 存储结果。
class Solution {
public:int numDistinct(string s, string t) {int ns.size(),mt.size();vectorvectordoubledp(m1,vectordouble(n1));for(int j 0; j n; j) dp[0][j] 1; // 初始化s s;t t;for(int i1;im;i){for(int j1;jn;j){if(s[j]t[i]){dp[i][j]dp[i][j-1]dp[i-1][j-1];}else{dp[i][j]dp[i][j-1];}}}return dp[m][n];}
}; 题目四—— 44. 通配符匹配 - 力扣LeetCode 嗯这个和我们的Linux里面的通配符是一模一样的啊 1.状态表示 对于两个字符串之间的DP问题我们通常的思考方式如下
将第一个字符串 s 的 [0, i] 区间和第二个字符串 p 的 [0, j] 区间作为研究对象。定义状态 dp[i][j] 来表示某种关系或属性这个关系或属性通常与 s 的前 i1 个字符和 p 的前 j1 个字符有关。
在这个上下文中我们可以定义 dp[i][j] 为
dp[i][j] 表示 s 的【0i】区间的字符串能否与 p 的【0j】区间的字符串相匹配。 2.推导状态转移方程 首先啊这种题目都是在最后一个字符做文章啊
一共有三种情况
当 s[i] p[j]或者p[j] ? 的时候当 p[j] * 的时候当 p[j] 不是特殊字符且不与 s[i] 相等时 当 s[i] p[j]或者p[j] ? 的时候此时两个字符串匹配上了当前的⼀个字 符只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个 状态中的匹配结果 dp[i][j] dp[i-1][j - 1] 当 p[j] * 的时候此时匹配策略有多种情况
* 匹配空字符串此时相当于它匹配了一个寂寞直接继承状态 dp 数组的前一个状态即 dp[i][j-1]此时 dp[i][j] dp[i][j - 1] * 匹配s字符串里的一个字符直接继承状态 dp 数组的前一个状态即dp[i-1][j-1]此时dp[i][j]dp[i-1][j-1] * 匹配s字符串里的两个字符时直接继承状态 dp 数组的前一个状态即dp[i-2][j-1]此时dp[i][j]dp[i-2][j-1] 那么匹配3个字符4个字符……啥的就不说了啊
* 向前匹配 1 ~ n 个字符直⾄匹配上整个 s 串。此时相当于 从 dp[k][j - 1] (0 k i) 中所有匹配情况中选择性继承可以成功的 情况。此时 dp[i][j] dp[k][j - 1] (0 k i) 优化当我们发现计算⼀个状态的时候需要⼀个循环才能搞定的时候我们要想到去优化。优化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来然后⽤数学的⽅式 做⼀下等价替换。 在这里我们发现只要这个dp[i][j] dp[k][j - 1] (0 k i) 只要dp[i][j] dp[k][j - 1] (0 k i) 里面任何一个是true那么dp[i][j]就是true。 当 p[j] * 时状态转移⽅程为dp[i][j] dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] ...... 但是当我们不断的修改i的值我们就会发现下面这个情况 dp[i][j] dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] ......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-1] 那不就很简单了吗循环也省去了。 当 p[j] 不是特殊字符且不与 s[i] 相等时⽆法匹配。 三种情况加起来就是所有可能的匹配结果。
当 s[i] p[j]或者p[j] ? 的时候此时dp[i][j]dp[i-1][j-1]当 p[j] * 的时候此时dp[i][j]dp[i-1][j]||dp[i][j-1]当 p[j] 不是特殊字符且不与 s[i] 相等时此时dp[i][j]false; 3. 初始化 我们知道状态转移方程会使用dp[i - 1][j - 1]那对于i0和j0的情况那这个dp[i - 1][j - 1]不是会越界吗为了防止这个情况的发生我们可以将dp表多开一行一列但是这样子会影响到和原数组的下标映射关系所以我们可以在原字符串前加一个空字符这样子就不会有下标映射的困扰了 为了防止大家搞混和原字符串的下标映射关系我们可以在原字符串前面加一个空字符。这样子下标映射就没有问题了。 由于 dp 数组的值设置为是否匹配为了不与答案值混淆我们需要将整个数组初始化为 false 。 由于需要⽤到前⼀⾏和前⼀列的状态我们初始化第⼀⾏、第⼀列即可。
dp[0][0] 表⽰两个空串能否匹配答案是显然的初始化为 true 。第⼀⾏dp[0][j]表⽰ s 是⼀个空串 p 串和空串只有⼀种匹配可能即 p 串表⽰为*** 此时也相当于空串匹配上空串。所以我们可以遍历 p 串把所有前导为 * 的p ⼦串和空串的 dp 值设为 true 。第⼀列表⽰ p 是⼀个空串不可能匹配上 s 串跟随数组初始化即可。 4. 填表顺序 从上往下填每⼀⾏每⼀⾏从左往右。 5. 返回值 根据状态表⽰返回 dp[m][n] 的 值。 class Solution {
public:bool isMatch(string s, string p) {int ms.size(),np.size();s s;p p;//初始化vectorvectorbooldp(m1,vectorbool(n1,false));dp[0][0]true;for(int j 1; j n; j){ if(p[j] *) {dp[0][j] true;}else {break;}}for(int i1;im;i){for(int j1;jn;j){if(s[i]p[j]||p[j]?){dp[i][j]dp[i-1][j-1];}else if(p[j]*){dp[i][j]dp[i-1][j]||dp[i][j-1];}}}return dp[m][n];}
}; 题目五——10. 正则表达式匹配 - 力扣LeetCode 我们仔细看一下题目
我觉得大家最不理解的就是这个*我来讲一下
*不能单独存在只能和它前面那个字符搭配使用a* 表示 a 可以出现零次或多次题目保证每次出现字符 * 时前面都匹配到有效的字符 1.状态表示 对于两个字符串之间的DP问题我们通常的思考方式如下
将第一个字符串 s 的 [0, i] 区间和第二个字符串 p 的 [0, j] 区间作为研究对象。定义状态 dp[i][j] 来表示某种关系或属性这个关系或属性通常与 s 的前 i1 个字符和 p 的前 j1 个字符有关。
在这个上下文中我们可以定义 dp[i][j] 为
dp[i][j] 表示 s 的【0i】区间的字符串能否与 p 的【0j】区间的字符串相匹配。 2.推导状态转移方程 首先啊这种题目都是在最后一个字符做文章啊
一共有三种情况
当 s[i] p[j]或者p[j] . 的时候当 p[j] * 的时候当 p[j] 不是特殊字符且不与 s[i] 相等时 当 s[i] p[j]或者p[j] . 的时候此时两个字符串匹配上了当前的⼀个字 符只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个 状态中的匹配结果 dp[i][j] dp[i-1][j - 1] 当 p[j] * 的时候和上道题稍有不同的是上道题 * 本⾝便可匹配 0 ~ n 个字符但此题是要带着 p[j - 1] 的字符⼀起匹配 0 ~ n 个和 p[j - 1] 相同的字 符。
按照上题的思路我们可能会像下面这样子干
p[j-1]* 变成空字符串这个时候我不需要管你s[i]是什么我直接将p[j-1]*设置为一个空串此时相当于它匹配了一个寂寞直接继承状态 dp 数组的前一个状态即 dp[i][j-2]此时 dp[i][j] dp[i][j - 2]
p[j-1]*匹配s字符串里的一个字符时此时p[j-1]s[i]或者p[j-1].直接继承状态 dp 数组的前一个状态即dp[i-1][j-2]此时dp[i][j]dp[i-1][j-2] p[j-1]* 匹配s字符串里的两个字符时此时p[j-1]s[i]或者p[j-1].直接继承状态 dp 数组的前一个状态即dp[i-2][j-2]此时dp[i][j]dp[i-2][j-2]
那么p[j-1]* 匹配3个字符4个字符……啥的就不说了啊
p[j-1]* 向前匹配 1 ~ n 个字符直⾄匹配上整个 s 串。此时相当于 从 dp[k][j - 1] (0 k i) 中所有匹配情况中选择性继承可以成功的 情况。此时 dp[i][j] dp[k][j - 2] (0 k i) 优化当我们发现计算⼀个状态的时候需要⼀个循环才能搞定的时候我们要想到去优化。优化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来然后⽤数学的⽅式 做⼀下等价替换。 在这里我们发现只要这个dp[i][j] dp[k][j - 2] (0 k i) 只要dp[i][j] dp[k][j - 2] (0 k i) 里面任何一个是true那么dp[i][j]就是true。 当 p[j] * 时状态转移⽅程为dp[i][j] dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] ...... 但是当我们不断的修改i的值我们就会发现下面这个情况 dp[i][j] dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 2][j - 2] ......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-2] 但是后面这个dp[i-1][j]是有前提的——p[j-1] s[i] || p[j-1] .。 dp[i][j] dp[i][j-2] || (dp[i-1][j] (p[j-1] s[i] || p[j-1] .)); 那不就很简单了吗循环也省去了。 当 p[j] 不是特殊字符且不与 s[i] 相等时⽆法匹配。 三种情况加起来就是所有可能的匹配结果。
当 s[i] p[j]或者p[j] ? 的时候此时dp[i][j]dp[i-1][j-1]当 p[j] * 的时候此时dp[i][j] dp[i][j-2] || (dp[i-1][j] (p[j-1] s[i] || p[j-1] .));当 p[j] 不是特殊字符且不与 s[i] 相等时此时dp[i][j]false 3. 初始化 由于 dp 数组的值用于表示是否匹配为了避免与答案值混淆我们需要将整个数组初始化为 false。由于需要用到前一行和前一列的状态我们需要特别初始化第一行和第一列。 dp[0][0] 表示两个空串能否匹配答案显然是 true因为空串与空串总是匹配的。 第一行是dp[0][j]这表示 s 是一个空串而 p 串和空串的匹配情况只有一种可能即 p 串全部字符表示为“ 任意字符 *”此时也相当于空串匹配上空串。所以我们可以遍历 p 串把所有前导为任⼀字符* 的 p ⼦串和空串的 dp 值设为 true 第一列表示 p 是一个空串此时不可能匹配上 s 串除非 p 本身就是一个空串或者由 * 组成的表示空串的模式但这种情况已经在第一行处理过了因此第一列除了 dp[0][0]应该全部初始化为 false。 4. 填表顺序 从上往下填每一行每一行从左往右。即按照 dp[i][j] 的顺序其中 i 从 0 到 ms 的长度j 从 0 到 np 的长度。 5. 返回值 根据状态表示最终返回 dp[m][n] 的值它表示 s 串和 p 串是否匹配。 class Solution {
public:bool isMatch(string s, string p) {int ms.size(),np.size();s s;p p;vectorvectorbooldp(m1,vectorbool(n1,false));//初始化dp[0][0] true; //本来应该是for(int i1;in;i2)的但是我们p p;//所以真正的第二个字符的下标是2for(int i2;in;i2){if(p[i] *) dp[0][i] true;elsebreak;}for(int i1;im;i){for(int j1;jn;j){if(s[i]p[j]||p[j].){dp[i][j]dp[i-1][j-1];}else if(p[j]*){dp[i][j] dp[i][j-2] || (dp[i-1][j] (s[i] p[j-1] || p[j-1] .));}}}return dp[m][n];}
}; 题目六——97. 交错字符串 - 力扣LeetCode 1.状态表示 对于两个字符串之间的 dp 问题我们⼀般的思考⽅式如下
选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象结合题⽬的要求来定义「状态表⽰」然后根据两个区间上「最后⼀个位置的字符」来进⾏「分类讨论」从⽽确定「状态转移 ⽅程」。
我们可以根据上⾯的策略解决⼤部分关于两个字符串之间的 dp 问题。 但是这道题目有3个字符串。我们的经验还能用吗应该是可以的 我们定了s1和s2的长度那肯定能知道此时它们能匹配上的s3的长度。
dp[i][j] 表示字符串 s1 的【0i】和字符串 s2 的【0j】能否拼接成字符串 s3 的【0ij-1】里面的字符。
大家可能看这个ij-1不太顺眼所以我们可以进行一下优化。
我们先把所有原字符串进行预处理也就是s1 s1, s2 s2, s3 s3 。
dp[i][j] 表示字符串 s1 的【1i】和字符串 s2 的【1j】能否拼接成字符串 s3 的【1ij】里面的字符。 2.推导状态转移方程 先分析⼀下题⽬题⽬中交错后的字符串为 s1 t1 s2 t2 s3 t3...... 看似⼀个 s ⼀个 t 。实际上 s1 能够拆分成更⼩的⼀个字符进⽽可以细化成 s1 s2 s3 t1 t2 s4...... 。 也就是说并不是前⼀个⽤了s 的⼦串后⼀个必须要⽤ t 的⼦串。这⼀点理解对我们的状态转移很重要。
继续根据两个区间上「最后⼀个位置的字符」结合题⽬的要求来进⾏「分类讨论」
注意下标是从1开始的
当s3[ij] s1[i]时 这意味着s3的当前最后一个字符与s1的当前最后一个字符匹配。因此为了判断整个字符串能否交错组成我们需要检查s1的前i-1个字符与s2的前j个字符是否能交错形成s3的前ij-1个字符即dp[i-1][j]。此时更新规则为dp[i][j] dp[i-1][j]如果s1的这部分与s2的已考虑部分能匹配s3的对应部分。当s3[ij] s2[j]时 这意味着s3的当前最后一个字符与s2的当前最后一个字符匹配。因此为了判断整个字符串能否交错组成我们需要检查s1的前i个字符与s2的前j-1个字符是否能交错形成s3的前ij-1个字符即dp[i][j-1]。此时更新规则为dp[i][j] dp[i][j-1]如果s2的这部分与s1的已考虑部分能匹配s3的对应部分。当s3[ij]既不等于s1[i]也不等于s2[j]时 这表明s3的当前最后一个字符既不能与s1的当前最后一个字符匹配也不能与s2的当前最后一个字符匹配。因此dp[i][j]在这种情况下必然为False因为无法通过添加s1或s2的下一个字符来形成s3的当前部分。
但是我们仔细思考一下s3[ij] s1[i]和s3[ij] s2[j]这两种情况任意一个满足都是符合条件的有的人可能就会像下面这样子写 // 检查s1的当前字符是否与s3的当前位置匹配并考虑前一个状态if (s1[i] s3[i j]) {dp[i][j] dp[i - 1][j];}// 检查s2的当前字符是否与s3的当前位置匹配并考虑前一个状态else if (s2[j] s3[i j]) {dp[i][j] dp[i][j - 1];}// 如果都不匹配则dp[i][j]保持为false默认初始化值 但是这只能判断到一种情况明显不对啊有人做出下面这个改进 // 检查s1的当前字符是否与s3的当前位置匹配并考虑前一个状态if (s1[i] s3[i j]) {dp[i][j] dp[i - 1][j];}// 检查s2的当前字符是否与s3的当前位置匹配并考虑前一个状态if (s2[j] s3[i j]) {dp[i][j] dp[i][j - 1];}// 如果都不匹配则dp[i][j]保持为false默认初始化值
那要是我s1[i]s2[j]s3[ij]dp[i-1][j]是true,dp[i][j-1]是false你不就炸了吗
我们接着改进 if(s1[i] s3[i j]||s2[j] s3[i j])
{dp[i][j] dp[i-1][j]||dp[i][j-1];
}
那要是我s1[i]s3[ij]dp[i-1][j]是false,dp[i][j-1]是true你不就炸了吗
接下来我告诉大家一种方法
所以我们只能是下面这个情况
dp[i][j] (s1[i] s3[i j] dp[i - 1][j])|| (s2[j] s3[i j] dp[i][j - 1]);
其实这括号里面最前面是表示这括号的值对应的情况后面部分则是这种情况里dp[i][j]应该被赋予的值。
大家看这个式子可能有点懵或者感觉有点晕
当s1[i] s3[i j]时s1[i] s3[i j]为trues1[i] s3[i j]||dp[i - 1][j]的值取决于dp[i - 1][j]如果dp[i - 1][j]是true那s1[i] s3[i j] dp[i - 1][j]就是true如果dp[i - 1][j]是false那s1[i] s3[i j] dp[i - 1][j]就是false当s2[j] s3[i j]时s2[j] s3[i j]为trues2[j] s3[i j]||dp[i][j-1]的值取决于dp[i][j-1]如果dp[i][j-1]是true那s1[i] s3[i j] dp[i][j-1]就是true如果dp[i][j-1]是false那s1[i] s3[i j] dp[i][j-1]就是false中间连接部分使用||的原因是只要上述条件中有一个成立dp[i][j]的结果就为True代表字符串 s1 的【1i】和字符串 s2 的【1j】能拼接成字符串 s3 的【1ij】里面的字符。 综上所述状态转移方程可以总结为
dp[i][j] (s1[i] s3[ij] dp[i-1][j]) || (s2[j] s3[ij] dp[i][j-1]) 3. 初始化过程 在进行动态规划填表之前我们需要对dp数组进行初始化。由于状态转移方程中涉及到了i-1和j-1位置的值因此我们需要特别注意“第一个位置”即dp[0][j]和dp[i][0]以及“第一行”和“第一列”的初始化。 dp[0][0]的初始化dp[0][0] true因为空串与空串相加仍然是一个空串所以它们能够匹配。 第一行的初始化 当s1为空串时即i0的情况但注意在数组中我们用dp[0][j]来表示其中j代表s2的【1j】区间的字符我们只需要考虑s2的【1j】区间的字符是否能匹配s3的【1j】区间的字符。状态转移方程为dp[0][j] (s2[j] s3[j] dp[0][j-1]); 第一列的初始化 当s1为空串时即j0的情况但注意在数组中我们用dp[i][0]来表示其中j代表s1的【1i】区间的字符我们只需要考虑s1的【1i】区间的字符是否能匹配s3的【1i】区间的字符。状态转移方程为dp[i][0] (s1[i] s3[i] dp[i-1][0]); 4. 填表顺序 根据状态转移方程我们需要按照“从上往下”的顺序逐行填写dp数组而在每一行内又需要“从左往右”地逐个填写元素。这样的填表顺序可以确保在计算每个dp[i][j]时其所依赖的前置状态dp[i-1][j]和dp[i][j-1]都已经被计算出来。 5. 返回值 最终我们需要返回dp[m][n]的值它表示s1的所有字符与s2的所有字符是否能够交错拼接成s3的所有字符。
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m s1.size(), n s2.size(); // 使用s1和s2的实际长度if (m n ! s3.size()) { return false;}// s3的长度应该在调用此函数之前就已经验证过是否等于mn但这里没有显式检查vectorvectorbool dp(m 1, vectorbool(n 1, false));// 为了方便索引给s1, s2, s3前都加一个空格相当于在dp数组中从1开始考虑字符s1 s1;s2 s2;s3 s3;// 初始化dp数组dp[0][0] true; // 空串空串能构成空串// 初始化第一列只考虑s1的情况for (int i 1; i m; i) {dp[i][0] (s1[i] s3[i] dp[i - 1][0]);}// 初始化第一行只考虑s2的情况for (int j 1; j n; j) {dp[0][j] (s2[j] s3[j] dp[0][j - 1]);}// 填充dp数组的其余部分for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] (s1[i] s3[i j] dp[i - 1][j])|| (s2[j] s3[i j] dp[i][j - 1]);}}// 返回结果return dp[m][n];}
}; 题目七——712. 两个字符串的最小ASCII删除和 - 力扣LeetCode 正难则反求两个字符串的最⼩ ASCII 删除和其实就是找到两个字符串中所有的公共⼦序列 ⾥⾯ ASCII 最⼤和。 面对求解两个字符串的最小ASCII删除和的问题我们可以转换思路通过寻找两个字符串中的所有公共子序列并计算这些公共子序列中的ASCII最大和来间接求解。这是因为最小ASCII删除和实际上等于两个字符串的总ASCII码和减去公共子序列的ASCII最大和的两倍。 1.状态表示 dp[i][j] 表示字符串 s1 的 [0, i] 区间以及字符串 s2 的 [0, j-1] 区间内的所有子序列中公共子序列的ASCII最大和。 2.状态转移方程 当 s1[i] s2[j] 时
应该在 s1 的 [0, i-1] 区间以及 s2 的 [0, j-1] 区间内找到一个公共子序列的最大和然后在其后添加一个 s1[i-1]或 s2[j-1]因为它们是相等的字符。
此时dp[i][j] dp[i-1][j-1] s1[i-1]注意这里 s1[i-1] 是字符需要转换为对应的ASCII值进行计算但为简化表述这里仍用 s1[i-1] 表示。
当 s1[i-1] ! s2[j-1] 时
公共子序列的最大和可能存在于以下三种情况中
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]
但由于前两种情况已经包含了第三种情况的可能性即不选择当前字符作为公共子序列的一部分因此只需考虑前两种情况下的最大值。
综上状态转移方程为dp[i][j] max(dp[i-1][j], dp[i][j-1]) 3.初始化 为了方便处理空串的情况我们在原始的 dp 表上额外增加一行和一列用于表示空串。
初始化时第一行和第一列的值都设为0因为当其中一个字符串为空时公共子序列的ASCII和为0。 4.填表顺序 从上往下逐行填写 dp 表每行从左往右填写。 5.返回值 根据状态表示我们不能直接返回 dp 表中的某个值。
首先找到 dp[m1][n1]注意这里 m 和 n 分别是 s1 和 s2 的长度由于我们增加了额外的行和列所以这里是 m1 和 n1它表示两个字符串的最长公共子序列的ASCII最大和。
然后统计两个字符串的总ASCII码和 sum。
最后返回 sum - 2 * dp[m1][n1]即为所求的最小ASCII删除和。 class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m s1.size(), n s2.size();vectorvectorint dp(m 1, vectorint(n 1));for (int i 1; i m; i)for (int j 1; j n; j) {if(s1[i-1]s2[j-1]){dp[i][j]dp[i-1][j-1]s1[i-1];}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}int sum 0; //统计元素和for(auto s : s1) sum s;for(auto s : s2) sum s;return sum - 2*dp[m][n];}
}; 题目八——718. 最长重复子数组 - 力扣LeetCode 子数组是数组中“连续”的一段我们习惯上“以某一个位置为结尾”来研究。由于是两个数组因此我们可以尝试以第一个数组的 i 位置为结尾以及第二个数组的 j 位置为结尾来解决问题。 1.状态表示 dp[i][j] 表示以第一个数组的 i 位置为结尾以及第二个数组的 j 位置为结尾的公共的、长度最长的“子数组”的长度。 2.状态转移方程 对于 dp[i][j]当 nums1[i-1] nums2[j-1]注意数组下标从0开始但dp数组下标从1开始所以这里是 i-1 和 j-1的时候才有意义。此时最长重复子数组的长度应该等于 1 加上除去最后一个位置时以 i-1, j-1 为结尾的最长重复子数组的长度。
因此状态转移方程为dp[i][j] 1 dp[i-1][j-1]当 nums1[i-1] nums2[j-1]否则 dp[i][j] 0。 3.初始化 添加一行和一列dp 数组的下标从 1 开始这样处理起来更方便无需额外判断越界。
第一行和第一列表示其中一个数组为空的情况此时没有重复子数组因此里面的值设置成 0。 4.填表顺序 根据状态转移我们需要从上往下填每一行每一行从左往右。 5.返回值 根据状态表示我们需要返回 dp 表里面的“最大值”。
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int m nums1.size(), n nums2.size();vectorvectorint dp(m 1, vectorint(n 1));int ret 0;for (int i 1; i m; i)for (int j 1; j n; j)if (nums1[i - 1] nums2[j - 1])dp[i][j] dp[i - 1][j - 1] 1, ret max(ret, dp[i][j]);return ret;}
};
