【动态规划】两个数组的 dp 问题二
两个数组的 dp 问题
- 1.正则表达式匹配
- 2.交错字符串
- 3.两个字符串的最小ASCII删除和
- 4.最长重复子数组
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.正则表达式匹配
题目链接： 10. 正则表达式匹配
题目分析：
算法原理：
经验 + 题目要求
dp[i][j] 表示：p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串
2.状态转移方程
根据最后一个位置的状况，分情况讨论
p[j] 属于 {a-z}，如果 i 位置 和 j 位置字符相等，并且 s [0, i - 1]能被 p[0, j -1] 匹配上，那 [0, i] 就能被 [0, j] 匹配上
p[j] == ‘.’ ，'.'可以匹配任何单个字符，因此只用去看s [0, i - 1]能否被 p[0, j -1] 匹配上
p[j] == ’ * ‘，（ ’ * ’ 匹配零个或多个前面的那一个元素。）’ * ’ 单独使用是没有意义的，它必须要和前面字符搭配起来使用。前面 j -1 位置字符有两种情况，要么是 {a - z}、要么是 ‘ . ’。
j - 1 位置字符是 ‘ . ’，相当于字符串是 " .* "，可以是空串， 可以是一个 ‘ . ’，可以是两个 ‘ . ’
如果是空串，我们就看dp[i][j-2]
如果p[j]匹配1个字符，我们就看dp[i-1][j-2]
如果p[j]匹配2个字符，我们就看dp[i-2][j-2]
…
dp[i][j] 时间复杂度就是O(N^2)，在加上p[j] == ’ * '，时间复杂度就是O(N^3)了。想个办法看看p[j] == ’ * '，能否由若干个有限的状态表示。
优化：
第一种方法：数学
p[j] == ‘*’，有这么多种情况，只要有一种情况为真就可以了，所以我们可以得到下面的等式。发现 j -2是不变的，让等式所有 i 都减1。然后就可以进行替换了。
第二种方法：根据状态表示以及实际情况，优化状态转移方程
p[j] == ‘*’，找到dp[i][j]。
当j位置是 ‘ * ’ ，注意 j-1 位置 ‘.’，然后对 " .* " 进行分析。
如果 " .* "，去抵消 i 位置，然后保留 " .* "，我们得到一个状态。可能会有疑问，我们这个组合分明可以干掉很多个，为什么干得一个之后保留只有这一种情况。其实在dp[i-1][j]状态里面，这个组合会继续尝试干掉i-1，因为这个状态里面p[j]依旧等于
‘ * ’。相当于这个状态已经帮我们做了下面的事情。
还有一种情况，如果 " .* " 匹配空串，相当于就是把这个组合舍去。
至此p[j] == ’ * '，j - 1 位置 是 ‘ . ’，情况我们才说完
当p[j] == ’ * '，j - 1 位置 是 {a-z}。
这里我们按照优化第二种方法分析：
" _* “，去匹配空串，相当于把” _* "舍去，
" _* "，去匹配一个，然后保留。不是说想匹配就去匹配，前提条件必须满足 s[i] == p[j-1] 才会有 dp[i-1][j]。
虽然我们状态转移方程情况这么多。但是我们可以总结一下：
3.初始化
- 引入空串
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
dp表上面多加一行表示s是空串，左边多加一列表示p是空串。接下来看看里面值应该填什么。
当 s 是空串，p也是空串，肯定能匹配上，所以第一行第一个格子是true
当s 是空串，但是 p 不是空串的话，注意 " _* ‘"可以匹配空串。现在就要对p的字符串就行讨论，然后初始化第一行后面的位置，如果s是空字符串，p字符串 前面如果出现’ _* ‘ 可以匹配空串，但是 ’ _* ‘ 之后出现 " __ "，后面不管有多少个’ _* '都不能匹配了。
现在考虑第一列，如果p是空串，s也是空串，肯定能匹配，所以第一列第一个空格还是true。
后续如果 p 是空串，s不是空串，肯定匹配不上，所以第一列后续都是false
下标映射有两种方法：
- dp表多加一行一列整体向右下移动一位，如果要回原表需要 i -1，j -1 才行
- s = ’ ‘ + s，字符串前面加一个辅助字符，这样字符串字符就和dp表一一对应了。
4.填表顺序
从上往下填写每一行，每一行从左往右
5.返回值
dp[i][j] 表示：p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串。题目要求是整个字符串，因此返回dp[m][n]，m是s的长度，n是p的长度
class Solution {
public:
bool isMatch(string s, string p) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
s = ' ' + s, p = ' ' + p;
dp[0][0] = true;
for(int j = 2; j <= n; j += 2)
if(p[j] == '*') dp[0][j] = true;
else break;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++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[m][n];
}
};
2.交错字符串
题目链接：97. 交错字符串
题目分析：
单看叙述很难理解，接下来我们借用例子理解一下。
这道题的意思是我们可以把字符串拆成若干份，然后把若干份拼接成s3。
比如下面先把s1拆分为aa，s2拆分成dbbc，在把s1剩余拆分为bc，在把s2剩余拆分a，在把s1剩余拆分为c。就能拼接成s3.
注意空串是有意义的。
算法原理：
之前做的字符串问题最多也就是两个字符串，但这道题出现了三个字符串，分别是s1、s2、s3。那之前的经验还能用吗？我们之前的经验是在两个字符串里面各选一段区间作为研究对象来研究问题。这三个字符串怎么办呢？其实我们依旧可以这个经验。我们选取s1、s2区间之后我们想把两个区间拼接形成s3。我们其实已经知道s1字符串长度，s2字符串长度了，那s3字符串长度其实也就固定了。也就是说当我们选取s1区间、s2区间，s3区间就已经被确定了。因此也可以用之前的经验 + 题目要求，来定义状态表示。
这里我们预处理一下，让字符串下标从1开始，这样等下下标对应就会非常简单。
1.状态表示
经验 + 题目要求
dp[i][j] 表示：s1中 [1，i] 区间内字符串以及 s2中 [1，j] 区间内字符串，能否拼接凑成 s3 [1，i+j]区间内的字符串
- 状态转移方程
根据最后一个位置的状况，分情况讨论
最后一个位置我们来看看这个s3，如果s1、s2能够交错拼成s3，那s3最后 i+j 位置元素， 要么等于 s1 最后 i 位置元素，要么等于 s2 最后 j 位置元素。要么都不相等。如果都不相等那就不用管了，创建dp时就已经处理了 。我们只研究能匹配的情况。
如果s1[i] == s3[i+j]，我们还需要去看 s1[1,i-1] 和 s2[1,j] 区间能否拼接s3[1, i+j-1]，正好是dp[i-1][j]
如果s2[j] == s3[i+j]，和上面一样
3.初始化
- 引入空串
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
dp表上面多加一行表示s1是空串，左边多加一列表示s2是空串。接下来看看里面值应该填什么。
s1是空串，s2是空串，i+j = 0，s3也是空串。空串和空串是可以拼接凑成空串的。所以第一行第一个位置填true
s1是空串，s2不是空串，s3也不是空串，如果s2字符串能够对应上s3，填ture，如果有一个字符不能对应，后面都填false
s2是空串，s1不是空串，s3也不是空串，同理如果s1字符串能够对应上s3，填ture，如果有一个字符不能对应，后面都填false
4.填表顺序
从上往下填写每一行，每一行从左往右
5.返回值
dp[m][n]
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int m = s1.size(), n = s2.size();
if(m + n != s3.size()) return false;
s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//第一行初始化
dp[0][0] = true;
for(int j = 1; j <= n; ++j)
if(s2[j] == s3[j]) dp[0][j] = true;
else break;
//第一列初始化
for(int i = 1; i <= m; ++i)
if(s1[i] == s3[i]) dp[i][0] = true;
else break;
//填表
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];
}
};
3.两个字符串的最小ASCII删除和
题目链接： 712. 两个字符串的最小ASCII删除和
题目分析：
返回 使两个字符串相等 所需删除字符的 ASCII 值的最小和。
算法原理：
在正式解决这道题之前，我们先看一下示例2，第二种删法Ascll码和最小，所以选择第二种。然后看一下删完之后留下来的字符串。是不是第二种删法留下来的字符串和是最大的。那现在能不能把上面问题转化一下，你让我找删除的最小和，是不是就是变相去找这两个字符串公共子序列里面Ascll码最大的那个。这两个字符串Ascll码总和是不变的，你让我找最小，其实就是变相去找公共子序列里面Ascll码和最大的。
分析：求两个字符串里面所有公共子序列里面，Ascll值的最大和。
这种方法也是我们常用的：正难则反。
1.状态表示
经验 + 题目要求
dp[i][j] 表示：s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有子序列里，公共子序列的 ASCll 最大和
2.状态转移方程
根据最后一个位置的状况，分情况讨论
我们要找公共子序列，是不是要从s1拿出来一个子序列，再从s2拿出来一个子序列，判断它们是不是公共子序列，然后把它们Ascll码求一下。然后继续在s1里拿一个，s2里拿一个。。。，把所有情况都找到然后求里面的最大值。
所有从s1拿一个子序列，在从s2那一个子序列有如下情况
-
有s1[i]，有s2[j]
-
有s1[i]，没有s2[j]
-
没有s1[i]，有s2[j]
-
没有s1[i]，没有s2[j]
然后求出这四种情况的最大值。
有s1[i]，有s2[j]，子序列是以它们俩为结尾的。如果是公共子序列是不是这里两个位置要相等啊 s1[i] == s2[j]，然后去s1[0, i - 1]，s2 [0, j - 1] 找公共子序列Ascll码最大值就是dp[i-1][j-1]，然后加上s1[i]的Ascll码或者s2[j]的Ascll码因为它俩Ascll码是一样的。
有s1[i]，没有s2[j] 可能会直接想用 dp[i][j - 1] 公共子序列最大Ascll码和。但是要注意一下这个状态表示， 表示的是[0, i] 区间内所有的子序列，[0, i]既有s[i]也可以没有s[i]，也就是说 情况2包含情况4。所以 s1[i]，没有s2[j] 不能直接和 dp[i][j - 1] 划等号。但是没关系，我们求得是一个最大和。管dp[i][j - 1]里面包不包含情况4，你只要包含情况2就可以了。因为我们最后求得是最大值，所有这里可以用dp[i][j - 1]。
同理情况3也是这样。
没有s1[i]，没有s2[j]，就是dp[i-1][j-1]，因为情况2、情况3包含情况4，所有可以不用考虑这种情况。
3.初始化
- 引入空串
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
4.填表顺序
从上往下填写每一行，每一行从左往右
5.返回值
状态表示求的是两个字符串的区间里面公共子序列的Ascll 最大和，题目要求两个字符串相等所需删除字符的 ASCII 值的最小和 。所以可以这样做
- 找到两个字符串中公共子序列的Ascll 最大和，dp[m][n]
- 统计两个字符串中Ascll和 -> sum
- sum - dp[m][n] * 2
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m + 1,vector<int>(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];
dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
}
int sum = 0;
for(auto ch : s1) sum += ch;
for(auto ch : s2) sum += ch;
return sum - 2 * dp[m][n];
}
};
4.最长重复子数组
题目链接： 718. 最长重复子数组
题目分析：
注意这道题，最长重复子数组，这与我们前面遇到两个数组dp子序列有点不一样。
子序列可以连续可以不连续，子数组一定要连续。
算法原理：
像之前两个数组dp问题，比如说最长公共子序列哪里，我们经验是选择第一个字符串[0, i]区间，第二个字符串[0, j]区间。然后把这两个区间作为研究对象，根据题目要求来定义状态表示。
这道题还是这样搞看一下有什么问题。
n1取[0, i]区间，n2取[0, j]区间，我要最长重复子数组。也就是说在n1这段区间找一下子数组，n2这段区间找一下子数组，然后把最长重复子数组长度统计一下。
选取[0, i]一段区间内的所有子数组，作为研究对象。
先想一想取某一段区间内所有子数组来研究 ，接下来推导下一个位置的时候，是不是得用到前面的状态，子数组这里有一个特性，在推i+1位置的时候，必须要跟在i位置后面才行。但是我们这个状态是选取选取[0, i]一段区间内的所有子数组而且是找那个最长的。但是最长的可能在[0, i]的中间，那研究i+1位置跟不了它的后面。所以说这个状态表示太大根本推不出来状态转移方程。研究i+1位置我们要先知道i位置的状态，也就是以i位置为结尾的i那个状态。而不是这个区间里所有子数组的状态 。
为什么子序列这里我们可以选一段区间来做呢？其实是子序列的话，在这个区间内的所有子序列，i+1都可以跟在后面，因为子序列不要求一定是连续的。但是i+1为子，这个区间选的子数组可能不能跟在后面。
1.状态表示
我们这个状态表示要能表示以 i 位置为结尾以及 j 位置为结尾的最长的那个子数组。所有dp可以这样表示
dp[i][j] 表示：nums1 中以 i 位置元素为结尾的所有的子数组以及 nums2 中以 j 位置为结尾的所有子数组中，最长重复子数组的长度。
2.状态转移方程
根据最后一个位置的状况，分情况讨论
我们要的是最长重复子数组，那以i位置结尾，以j位置结尾，这两个位置是不是可能相等也有可能不相等。
相等可以找到重复子数组，如果都不想等那以i和j为结尾根本就没有重复子数组。
不相等，重复子数组长度为0
相等，是不是要先找到以 i -1位置为结尾的和以 j - 1位置为结尾的。因为相等可以跟在i-1后面或者j-1后面形成更长的。所以要先找到以i-1为结尾以及j-1为结尾的最长的子数组长度，然后在后面加上nums1[i]或者nums2[j]
3.初始化
- 上面多开一行，左边多开一列，这样填表就不要越界了。
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
我们可以根据空数组的定义来，填第一行，第一列的值。第一行表示第一个数组为空，第一行数组为空根本找不到重复子数组，所以第一行都是0，同理，第一列数组为空也根本找不到重复子数组，所以第一列都是0
4.填表顺序
根据状态转移方程。从上往下填写每一行。
5.返回值
我们的状态表示是以某个位置为结尾。所以我们要找到 dp 表里面的最大值。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(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;
}
};