💕"低头要有勇气，抬头要有底气。"💕
作者：Mylvzi
文章主要内容：算法系列–两个数组的dp问题(1)
大家好,今天为大家带来的是
算法系列--两个数组的dp问题(1),两个数组的dp问题在动态规划问题中属于较难的部分,状态转移方程不易推导,希望大家通过下面的几道题目能够掌握
1.最长公共子序列
链接:
https://leetcode.cn/problems/longest-common-subsequence/description/
分析:
题目要找的是两个字符串中,公共子序列的最长长度,也就是要找最长的公共子序列
既然是两个字符串,我们很容易想到dp表应该是一个二维的dp表
dp[i][j]中i是str1的下标,j是str2的下标
根据经验,我们会设出这样的状态表示
dp[i][j]表示str1以i位置为结尾的区间和str2以j位置为结尾的区间内,公共子序列的最长长度
如果以这个状态表示去分析状态转移方程,就会发现错误:
- 如果
s[i] == s[j],则可以构成公共子序列,此时只需在i-1和j-1区间内求得最长的公共子序列的长度然后再加上1即可,所以dp[i][j] = dp[i - 1][j - 1] + 1 - 如果
s[i] != s[j],此时就无法构成公共子序列,但是状态表示明确指出str1必须以i为结尾,str2必须以j为结尾,也就是公共子序列必须以这两个字符为结尾,逻辑矛盾,无法求出状态转移方程
所以我们要想办法更新一个状态转移方程,分析上述过程,最大的矛盾点在于两个公共子序列不能严格的按照以xxxx为结尾的形式表示,而是应该不限制子序列的开始结束位置,所以可以将状态表示设置为如下:
dp[i][j]:表示str1[0,i]区间内的字符串和str2[0,j]区间内的字符串中,最长的公共子序列的长度
状态转移方程推导:
- 如果
s[i] == s[j],则这两个区间内最长的公共子序列一定以(i,j)为结尾;可以利用反证法证明- 如果不是以
(i,j)为结尾,那么最长的公共子序列可以在内部,但是又由于s[i]==s[j],他们俩也算是公共子序列的一部分,所以还是以s[i]为结尾 - 还有可能是以(i,j)中一个下标为结尾,另一个不是最长公共子序列的结尾,但是由于,此时还是一定以(i,j)为结尾的
- 如果不是以
- 如果
s[i] != s[j],也就是结束的两个字符不同,则最长的公共子序列一定不以这两个位置为结尾,而是以i或者j之前的区间内的某一个位置为结尾,可以分三种情况:- [i-1][j]
- [i][j - 1]
- [i - 1][j - 1]
dp[i][j]应取这三种情况的最大值
初始化
初始化的目的就是为了防止越界,本题可能出现越界的情况是当i,j为0时
对于二维dp的问题,最常用的一种初始化的方式就是增加一行,增加一列-->dp[m + 1][n + 1]
增加之后就要考虑如何为这些位置赋值了,我们赋值的原则应该是:赋的值应该对之后的填表无影响,或者根据dp表所表示的实际的意义去赋值,本题就利用到这样的想法
试想,第一行表示i==0的情况,此时str1为空字符串(注意下标之间的映射关系),那么根据dp表的含义,此时两个字符串之间不存在公共的子序列,进而也不存在最长的公共子序列长度这一说,所以第一行的所有值应该赋值为0,同样的第一列也要赋值为0
还需要注意的一点是:如果我们扩增了dp表,则dp表与源字符串之间的映射关系发生改变,dp[i + 1] = str[i],dp表的i位置对应的是字符串的的i-1位置,其实这里也可以做一个小优化(字符串的dp问题经常会使用这样的优化),就是让原先的字符串扩增1,str1 = " " + str1,str2 = " " + str2,让两个字符串都拼接一个空格字符,这样他们的长度就+1了,此时dp表的i下标对应的就是字符串的i下标
填表顺序
易得:从上往下,从左至右
返回值
return dp[m][n]
- m == str1.length();
- n == str2.length();
代码实现:
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 1.创建dp表
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// 2.初始化
text1 = " " + text1;
text2 = " " + text2;
char[] s1 = text1.toCharArray();
char[] s2 = text2.toCharArray();
// 3.填表
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
}
}
// 4.返回值
return dp[m][n];
}
}
2.不相交的线
链接:
https://leetcode.cn/problems/uncrossed-lines/
分析:
本题的思路和"最长的公共子序列"那道题目的解法相同
代码:
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
// 本题的思路和"最长的公共子序列"那道题目的解法相同
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
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;
else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
}
}
return dp[m][n];
}
}
3.不同的⼦序列
链接:
https://leetcode.cn/problems/distinct-subsequences/submissions/516072259/
分析:
对于两个字符串,公共序列xxxx之类的问题,我们用经验来作为状态表示,本题的状态表示:
- dp[i][j]:表示s字符串[0,j]区间内包含多少个t字符串[0,i]区间的字符
首先,这个状态表示能返回最终的结果么?可以的,走到最后,就表示s整个字符串内包含多少个t字符串,刚好和题目要求相同
接着分析状态转移方程,对于本题状态转移方程还是有所不同的,首先由于是在s中找有多少个t这样的要求,那么t一定是较小的那个,对于t字符串来说,每次推导状态,都必须包含i位置的字符,注意不是找有多少个公共序列,而是找s中包含多少个t
状态转移方程的推导一般都是根据最后一个状态进行划分,对于t来说,其状态是固定的,不用考虑,对于s来说需要分类讨论,因为包不包含最后一个位置的字符是对整个状态有影响的,所以可以分为以下两种情况
- 包含s[j]:也就是s字符串的子序列必须以j位置的字符结尾,那么此时dp[i][j]的生效就有条件了,必须t[i] == s[j],dp[i][j]才能生效,且
dp[i][j] = dp[i - 1][j - 1] - 不包含 s[j]:在s字符串的[0,i-1]区间内找t字符串[0,i]出现的次数
初始化
还是根据经验,二维的dp一般选择增加一行一列的方式来规避越界,第一行表示i == 0,即t字符串为空串,所以第一行全部初始化为1,第一列表示j == 0,即s字符串为空串,第一行全部初始化为0
返回值
易得返回dp[m][n]
代码:
class Solution {
public int numDistinct(String s, String t) {
// 特殊判断
if(t.length() > s.length()) return 0;
// 创建dp表并初始化
int m = t.length();
int n = s.length();
int[][] dp = new int[m + 1][n + 1];
for(int j = 0; j <= n; j++) dp[0][j] = 1;
t = " " + t;
s = " " + s;
char[] tt = t.toCharArray();
char[] ss = s.toCharArray();
// 填表
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = tt[i] == ss[j] ? (dp[i][j - 1] + dp[i - 1][j - 1]) : dp[i][j - 1];
}
}
return dp[m][n];
}
}
4.通配符匹配
链接:
https://leetcode.cn/problems/wildcard-matching/
分析:
代码:
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// 2.初始化
dp[0][0] = true;
for(int j = 1; j <= n; j++){
if(p.charAt(j - 1) == '*') dp[0][j] = true;
else break;
}
s = " " + s;
p = " " + p;
char[] ss = s.toCharArray();
char[] pp = p.toCharArray();
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(pp[j] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else dp[i][j] = (ss[i] == pp[j] || pp[j] == '?') && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
}
本题的难点就在于当p[j] == '*'时可以匹配任意的子序列 ,那么就有很多种的状态表示,要想办法使用若干个状态去表示.
5. 正则表达式
链接:
https://leetcode.cn/problems/regular-expression-matching/
分析:
初看本题觉得和上一题通配符匹配很相似,于是直接C,V结果发现无法通过(大胆),经过仔细分析发现本题在p[j] == '*'这种情况和上一题不同,上一题的*可以匹配任意的子序列,也就是他的状态是不受到之前状态的影响的,但是本题不一样,题目中明确告知*必须和前一个字符结合才有意义
也就是说,如果p[j] == *,其状态会受到p[j - 1]的影响,所以对于这种情况要单独讨论
一定要注意
*可以匹配空串,此时就代表这两个位置的字符无效了
初始化:
本题的初始化和通配符匹配也有所不同,还是那句话,这道题当p[j]==*时的状态是受到前一个字符的影响的
注意本题是不会出现多个*连续出现的,题目规定一个*之前一定有一个有效的字符去进行匹配
代码:
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// 2.初始化(注意细节)
dp[0][0] = true;
for(int j = 2; j <= n; j+= 2){
if(p.charAt(j - 1) == '*') dp[0][j] = true;
else break;
}
s = " " + s;
p = " " + p;
char[] ss = s.toCharArray();
char[] pp = p.toCharArray();
// 填表
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(pp[j] != '*') dp[i][j] = (ss[i] == pp[j] || pp[j] == '.') && dp[i - 1][j - 1];
else dp[i][j] = dp[i][j - 2] || (pp[j - 1] == '.' || pp[j - 1] == ss[i]) && dp[i - 1][j];
}
}
// 返回值
return dp[m][n];
}
}
总结:
- 两个数组的dp问题经常是
两个字符串之间关系,比如公共子序列的长度,能够匹配多少个目标字符串之类的 - 两个字符串的问题也有一些常用的经验和优化
- 状态表示一般都是
s1[0,1]区间内,s2[0,j]区间内巴拉巴拉,比如s1.s2在不同的区间时的最长公共子序列的长度,又或者s2在在不同区间内能包含多少个s1特定区间内的字符串这样的问题,和之前我们惯用的以i位置为结束的状态表示不同 - 状态转移方程的推到比较难,要结合具体的题目尽心分析,但是大致的方向都相同,即
根据最后一个位置的状态去分类讨论 - 在初始化时往往要
引入空串,来应对下标之间的映射关系.对于dp表往往采取增加一行一列的方式进行初始化 - 返回值一般就是返回dp表中最后一个元素
- 状态表示一般都是
