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