目录
动态规划_两个数组的 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. 状态表⽰：
对于两个数组的动态规划，我们的定义状态表⽰的经验就是：
我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥
3. 初始化：
4. 填表顺序：
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