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

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

news 2025/9/17 20:54:44

目录

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

DeepSeek 赋能智慧能源：微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

编程新知 2025/6/15 19:07:20

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（33）：にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（33）：にする 1、前言（1）情况说明（2）工程师的信仰2、知识点（1）　にする1，接续：名词＋にする2，接续：疑问词＋にする3，（A）は（B）にする。（2）復習：（1）复习句子（2）ために　＆　ように（３）そう（４）にする3、…...

编程新知 2025/6/17 10:46:36

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

编程新知 2025/9/10 3:41:08

linux 错误码总结

1，错误码的概念与作用 在Linux系统中，错误码是系统调用或库函数在执行失败时返回的特定数值，用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递，errno由操作系统维护，保存最近一次发生的错误信息。值得注意的是，errno的值在每次系统调用或函数调用失败时…...

编程新知 2025/9/16 22:48:47

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

编程新知 2025/8/19 5:37:33

让AI看见世界：MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

编程新知 2025/8/25 20:08:49

华为云Flexus+DeepSeek征文｜DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

编程新知 2025/8/29 21:22:21

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达，从日常对话到特定领域的文档（例如医学文档）（Heritage 2013；Landmark、Gulbrandsen 和 Svenevei…...

编程新知 2025/9/13 17:40:39

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

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

编程新知 2025/9/13 17:39:30

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

编程新知 2025/8/17 7:11:57