当前位置： 首页 > news >正文

手机网站建设动态/百度竞价代理公司

news 文章来源：https://blog.csdn.net/2301_80636070/article/details/144257516 2025/3/11 2:24:58
手机网站建设动态,百度竞价代理公司,小程序制作定制开发,中山的网站建设目录 动态规划_两个数组的 dp （含字符串数组） 1. 最⻓公共⼦序列（medium） 解析： 1. 状态表⽰： 2. 状态转移⽅程： 3. 初始化：​编辑 4. 填表顺序：​编辑 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 n=s1.size(),m=s2.size();s1=" "+s1;s2=" "+s2;vector<vector<int>> dp(n+1,vector<int>(m+1));int ret=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;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(vector<int>& nums1, vector<int>& nums2) {//最长公共子序列int n=nums1.size(),m=nums2.size();vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;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 n=t.size(),m=s.size();vector<vector<double>> dp(n+1,vector<double>(m+1));for(int i=0;i<=m;i++)dp[0][i]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;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 n=s.size(),m=p.size();vector<vector<bool>> dp(n+1,vector<bool>(m+1));s=" "+s,p=" "+p;dp[0][0]=true;for(int i=1;i<=m;i++){if(p[i]=='*') dp[0][i]=true;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;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();vector<vector<int>> dp(n+1,vector<int>(m+1));p = " " + p, s = " " + s;dp[0][0]=true;for(int i=2;i<=m;i+=2){if(p[i] == '*') dp[0][i]=1;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;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;vector<vector<int>> dp(n + 1, vector<int>(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 n=s1.size(),m=s2.size();s1=" "+s1,s2=" "+s2;int ret=0;for(int i=1;i<=n;i++) ret+=(s1[i]);for(int i=1;i<=m;i++) ret+=(s2[i]);vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;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(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();vector<vector<int>> dp(n+1,vector<int>(m+1));int ret=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;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;}
};

总结：

有过前面子数组和子序列的总结，我觉得我自身是得到了质的飞跃~，现在再看这种题也已是题中人了嘿嘿嘿，加油！

总结不易~本章节对我的收获很大，希望对你也是~！！！

相关文章：

专题二十五_动态规划_两个数组的 dp （含字符串数组）_算法专题详细总结

目录 动态规划_两个数组的 dp &#xff08;含字符串数组&#xff09; 1. 最⻓公共⼦序列&#xff08;medium&#xff09; 解析&#xff1a; 1. 状态表⽰&#xff1a; 2. 状态转移⽅程&#xff1a; 3. 初始化&#xff1a;​编辑 4. 填表顺序&#xff1a;​编辑 5. 返回值…...

编程日记 2024/12/9 5:52:21

PHP语法学习(第七天)-循环语句，魔术常量

老套路了&#xff0c;朋友们&#xff0c;先回忆昨天讲的内容PHP语法学习(第六天)主要讲了PHP中的if…else语句、关联数组以及数组排序。 想要学习更多PHP语法相关内容点击“PHP专栏&#xff01;” 下列代码都是在PHP在线测试运行环境中得到的&#xff01;&#xff01; 还记得电…...

编程日记 2024/12/9 5:51:20

数据库授权讲解一下

这条 SQL 命令是 MySQL 数据库中用于权限管理的 GRANT 语句。它用于授予用户特定的权限。下面是命令的详细解释&#xff1a; GRANT ALL PRIVILEGES ON *.* TO root% IDENTIFIED BY Zz&#xff01;12345678 WITH GRANT OPTION;GRANT&#xff1a; 这是一个关键字&#xff0c;用于…...

编程日记 2024/12/9 5:49:17

组件开发的环境准备： nodejs安装，npm镜像源的修改，pnpm包管理器的安装（全局安装），基于pnpm创建脚手架项目

Node.js 是一个开源的、跨平台的 JavaScript 运行环境&#xff08;本质是Chrome引擎的封装&#xff09;,允许开发者使用 JavaScript 来编写服务器端代码 npm(Node Package Manager)是 Node.js 包管理器, 用来安装各种库、框架和工具 【Node.js官网】 https://nodejs.org 【n…...

编程日记 2024/12/9 5:46:14

学生成绩统计系统

实验内容 问题描述: 输入n个学生的考试成绩&#xff0c;每个学生信息由姓名与分数组成;试设计一种算法: (1)按分数高低次序&#xff0c;打印出每个学生的名次&#xff0c;分数相同的为同一名次; (2)按名次输出每个学生的姓名与分数。 基本要求: (1)学生的考试成绩必须通过…...

编程日记 2024/12/9 5:45:13

【Spring项目】图书管理系统

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;项目实现准备 1&#xff1a;需求 &#xff08;1&#xff09;登录 2&#xff1a;准备…...

编程日记 2024/12/9 5:44:12

Vivado ILA数据导出MATLAB分析

目录 ILA数据导出 分析方式一 分析方式二 有时候在系统调试时&#xff0c;数据在VIVADO窗口获取的信息有限&#xff0c;可结合MATLAB对已捕获的数据进行分析处理 ILA数据导出 选择信号&#xff0c;单击右键后&#xff0c;会有export ILA DATA选项&#xff0c;将其保存成CS…...

编程日记 2024/12/9 5:42:10

【开源免费】基于SpringBoot+Vue.JS高校学科竞赛平台（JAVA毕业设计）

博主说明&#xff1a;本文项目编号 T 075 &#xff0c;文末自助获取源码 \color{red}{T075&#xff0c;文末自助获取源码} T075&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…...

编程日记 2024/12/9 5:41:09

【机器学习】——windows下安装anaconda并在vscode上进行配置

一、安装anaconda 1.进入清华的镜像网站&#xff0c;下载自己电脑对应的anaconda版本。网站&#xff1a;https://repo.anaconda.com/archive/ 这里我下载的版本是anaconda3-2024.10-1-Windows-x86-64 2.下载完毕后开始安装anaconda 3.配置anaconda环境变量 在设置中找到编…...

编程日记 2024/12/9 5:40:08

【H2O2|全栈】Node.js与MySQL连接

目录 前言 开篇语 准备工作 初始配置 创建连接池 操作数据库 封装方法 结束语 前言 开篇语 本节讲解如何使用Node.js实现与MySQL数据库的连接&#xff0c;并将该过程进行函数封装。 与基础部分的语法相比&#xff0c;ES6的语法进行了一些更加严谨的约束和优化&#…...

编程日记 2024/12/9 5:37:05

汽配行业数字化解决方案（一）

汽配行业数字化解决方案&#xff0c;是通过整合云计算、大数据、人工智能、物联网等先进技术&#xff0c;构建一个全面、高效、智能的数字化生态系统&#xff0c;以实现汽配供应链的全程可视化与智能化管理。该解决方案涵盖了从供应商管理、库存优化、订单处理、物流跟踪到客户…...

编程日记 2024/12/9 5:36:03

前端路径“@/“的使用和配置

环境&#xff1a;vitets 需要安装types/node npm install types/node --save-dev在tsconfig.json中添加 如果有tsconfig.app.json和tsconfig.node.json文件&#xff0c;则在app.json中添加 "compilerOptions": {"baseUrl":".","paths&q…...

编程日记 2024/12/9 5:35:02

动态规划子序列问题系列一＞最长递增子序列

题目&#xff1a; 解析&#xff1a; 代码&#xff1a; public int lengthOfLIS(int[] nums) {int n nums.length;int[] dp new int[n];int ret 1;//最坏情况为1//初始化for(int i 0; i < n; i) dp[i] 1;for(int i 1; i < n; i){for(int j 0; j < i-1; j)if(…...

编程日记 2024/12/9 5:34:00

链表头文件大更新！！！

引言 原文章:链表简介及自制链表操作头文件_自己写一个链表头文件-CSDN博客。 此次更新添加了更多功能&#xff0c;让改头文件更 人性化 。 安装教程见原文章。 介绍 linked_list.h 头文件 linked_list.h 是一个 C 头文件&#xff0c;定义了一个模板类 LinkedList&#xff…...

编程日记 2024/12/9 5:32:59

力扣3381.长度可被K整除的子数组的最大元素和

力扣3381.长度可被K整除的子数组的最大元素和 题目 题目解析及思路 题目要求返回一段长度为K的倍数的最大子数组和 同余前缀和 代码 class Solution { public:long long maxSubarraySum(vector<int>& nums, int k) {int n nums.size();vector<long long>…...

编程日记 2024/12/9 5:30:57

http.ServeMux多路复用器的设置

package mainimport ("fmt""net/http" )func first(w http.ResponseWriter, r *http.Request) {fmt.Fprintln(w, "多函数-first") }func second(w http.ResponseWriter, r *http.Request) {fmt.Fprintln(w, "多函数-second") }func ma…...

编程日记 2024/12/9 5:29:56

优化器与优化方法：在现代科学与工程中的应用

目录 ​编辑 优化器&#xff1a;机器学习中的参数调整 1. 梯度下降系列 2. 动量法&#xff08;Momentum&#xff09; 3. Adagrad 4. RMSprop 5. Adam 优化方法&#xff1a;寻找系统最优解 线性规划 非线性规划 凸优化 非凸优化 结论 在当今的科学和工程领域&#…...

编程日记 2024/12/9 5:28:55

笔记本外接显示屏没声音

1、笔记本正常有声音&#xff0c;但是外接显示屏后没有声音了怎么回事呢&#xff1f;原来外接显示屏后笔记本的声音输出会自动选择显示屏的音频输出&#xff0c;但是显示屏可能没有声音输出所以导致笔记本没有声音。 2、解决办法&#xff1a;打开笔记本设置&#xff0c;选择声…...

编程日记 2024/12/9 5:27:54

vue框架

Vue.js是一种用于构建用户界面的JavaScript框架。它是一个轻量级框架&#xff0c;被设计为逐渐采用的渐进式框架&#xff0c;可以与现有项目集成&#xff0c;也可以作为一个完整的单页应用程序框架使用。 Vue.js具有以下特点&#xff1a; 简单易学&#xff1a;Vue.js的API简单…...

编程日记 2024/12/9 5:25:51

Vue指令（一）--v-html、v-show、v-if、v-else、v-else-if、v-on、v-bind、v-for、v-model

目录 &#xff08;一&#xff09;初识指令和内容渲染指令v-html 1.v-html 案例&#xff1a; 官网的API文档 &#xff08;二&#xff09;条件渲染指令v-show和v-if 1. v-show 2. v-if &#xff08;三&#xff09;条件渲染指令v-else和v-else-if 案例 &#xff08;四…...

编程日记 2024/12/9 5:24:49

ElK 8 收集 MySQL 慢查询日志并通过 ElastAlert2 告警至飞书

文章目录 1. 说明2. 启个 mysql3. 设置慢查询4. filebeat 设置5. 触发慢查询6. MySQL 告警至飞书 1. 说明 elk 版本&#xff1a;8.15.0 2. 启个 mysql docker-compose.yml 中 mysql&#xff1a; mysql:# restart: alwaysimage: mysql:8.0.27# ports:# - "3306:3306&q…...

编程日记 2024/12/9 5:22:46

QT通过在线安装器安装【详细】

在线安装器地址&#xff1a; 官方在线安装器&#xff1a;Index of /official_releases/online_installers (qt.io) 通过命令行启动安装页面 直接双击qt安装程序&#xff0c;在线安装会非常慢&#xff0c;甚至安装失败&#xff0c;所以通过命令行页面启动安装页面。点击wind…...

编程日记 2024/12/9 5:21:45

34.1 uber开源的m3db简介

本节重点介绍 : m3db自己的定位m3db自己的架构m3db自己的组件 两句话简介 M3最初是在优步开发的&#xff0c;目的是提供对优步业务运营&#xff0c;微服务和基础架构的可视性由于M3具有轻松进行水平扩展的能力&#xff0c;因此它为所有监视用例提供了一个集中式存储解决方案…...

编程日记 2024/12/9 5:18:40

MATLAB 最小二乘点云拟合球 （89）

MATLAB 最小二乘点云拟合球 （89） 一、算法介绍二、算法实现1.代码2.结果这是缘，亦是最美的相见 一、算法介绍 球面拟合算法是一种通过数学方法将一组三维点（通常在三维空间中分布）拟合到一个理想的球形表面上。这个过程通常涉及使用最小二乘法来最小化实际数据点与拟合的…...

编程日记 2024/12/9 5:17:39

【Altium Designer 】AD如何使用嘉立创元器件的3D封装

1.下载3D封装 以STM32F407VGT6为例&#xff0c;进入嘉立创商城网站&#xff0c;找到需要的元器件封装 复制编号&#xff0c;打开嘉立创EDA&#xff0c;编译器选择专业版&#xff0c;新建工程&#xff0c;点击PCB1 复制编号在搜索框中&#xff0c;点击搜索&#xff0c;然后放置…...

编程日记 2024/12/9 5:13:35

G15沈海高速茶白高架自动化监测

1. 项目简介 G15 沈海高速公路北起辽宁省沈阳市苏家屯区金宝台枢纽&#xff0c;与沈阳市绕城高速公路&#xff08;国家高速 G1501&#xff09;相接&#xff0c;南至海南省海口市秀英区粤海枢纽&#xff0c;与海南地区环线高速公路&#xff08;国家高速 G98&#xff09;相交&am…...

编程日记 2024/12/9 5:08:29

网站从渗透到mssql提权全过程

2|0渗透全过程 1.信息收集-端口探测 1&#xff09;Nmap端口探测&#xff1a;namp -sS -p 1-65535 172.16.12.103 可以看到端口开放情况 2.判断系统情况 根据端口情况初步判定为IISmssql.net系统&#xff0c;访问web站点URL应该为&#xff1a;http:172.16.12.103:27689 访问…...

编程日记 2024/12/9 5:00:22

Qt多线程与QTimer详解

引用 Qt多线程中使用QTimer&#xff08;常见问题汇总&#xff09; [多线程]多线程使用QTimer Qt::ConnectionType&#xff1a;Qt不同类型connect的详细区别说明与应用 Qt的4种多线程实现方式 一文搞定之Qt多线程(QThread、moveToThread) QTimer The QTimer class provides repe…...

编程日记 2024/12/9 4:58:18

基于stm23的智慧宿舍系统 （DAY10）_小程序

好久没记录开发进度了&#xff0c;今天小程序差不多开发完了&#xff0c;UI这块算是比较常见了&#xff0c;主要功能是能连接onenet查看设备上传的数据&#xff0c;同时也能对设备进行一些控制下面是几个主要的函数&#xff0c;功能比较简单 wx.request({url: ${apiBaseUrl}/t…...

编程日记 2024/12/9 4:56:16

深入理解Spring事务

目录 什么是Spring事务为什么需要Spring事务Spring事务的实现 Spring事务的传播机制Spring事务的底层原理 EnableTransactionManagement --开启Spring管理事务Import(TransactionManagementConfigurationSelector.class) --提供两个beanAutoProxyRegistrar --启用AOP的功能&am…...

编程日记 2024/12/9 4:53:12