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

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

news 2025/7/12 22:53:51

目录

动态规划_两个数组的 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

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

编程新知 2025/7/12 16:52:53

Zustand 状态管理库：极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

编程新知 2025/7/11 9:38:18

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

编程新知 2025/7/12 8:04:46

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

编程新知 2025/7/8 17:08:17

以光量子为例，详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

编程新知 2025/7/5 12:24:36

Linux离线（zip方式）安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

编程新知 2025/6/16 16:58:04

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

编程新知 2025/7/7 5:46:30

JS设计模式(4)：观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

编程新知 2025/7/6 11:26:45

C++.OpenGL （20/64）混合（Blending）

混合（Blending） 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

编程新知 2025/7/6 20:05:42

纯 Java 项目（非 SpringBoot）集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

编程新知 2025/7/9 6:12:46