解决两个数组的dp问题的常用状态表示:
1、选取第一个字符串[0-i]区间以及第二个字符串[0,j]区间作为研究对象
2、根据题目的要求确定状态表示
字符串dp的常见技巧
1、空串是有研究意义的,引入空串可以帮助我们思考虚拟的边界如何进行初始化。
2、如果我们的dp多开了一行一列,可以在字符串的前面多加上一个空格(s=“ ”+s),这样可以保证dp数组和字符串数组的下标映射关系是一一对应的,方便我们书写代码
一、最长公共子序列(模版)
. - 力扣(LeetCode)
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示:s1的[0,i]区间以及s2的[0,j]区间内的所有子序列中,最长公共子序列的长度。
2、状态转移方程
dp[i][j]: (从最后一个位置的状况去分情况讨论)
(1)s[i]==s[j]——>dp[i-1][j-1]+1
(2)s[i]!=s[j]——>max(dp[i-1][j],dp[i][j-1])
注意:dp[i-1][j]和dp[i][j-1]都包含了dp[i-1][j-1]的情况,但是该题只需要找最大值而不是统计个数,所以不必在意。
3、初始化
多开一行一列,引入空串去研究边界,均初始化为0即可。
4、填表顺序
从上往下填每一行
每一行从左往右填
5、返回值
dp[m][n]
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//字符串技巧
int m=text1.size(),n=text2.size();
text1=" "+text1, text2=" "+text2;
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(text1[i]==text2[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[m][n];
}
};
二、不相交的线
. - 力扣(LeetCode)
该题其实等价于最长公共子序列
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2)
{
//相当于是最长公共子序列
int m=nums1.size(),n=nums2.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(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[m][n];
}
};
三、不同的子序列
. - 力扣(LeetCode)
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示:s的[0,j]区间的所有子序列中,有多少个t的[0,i]区间内的子串
2、状态转移方程
dp[i][j]: (从s的子序列最后一个位置是否包含s[j])
(1)包含s[j]——>t[i]==s[j]——>+=dp[i-1][j-1]
(2)不包含s[j]——>+=dp[i][j-1]
3、初始化
引入空串去思考:
当s和t都为空串时,应该为1
当s为空串,t不为空串的时候,应该为0
当t为空串,s不为空串的时候,应该为1
所以t为空串时,也就是i=0(第一行) 应该都初始化为1 而其他位置则是0
4、填表顺序
从上往下填每一行
每一行从左往右填
5、返回值
dp[m][n]
6、细节处理
该题可能会越界,所以用double去存储。
class Solution {
public:
int numDistinct(string s, string t) {
//s字符串0-j中所有子序列中 有多少个t字符串内0-i区间内的子串
int m=t.size(),n=s.size();
vector<vector<double>> dp(m+1,vector<double>(n+1)); //会越界 double>long long
//分析最后一位的状态 t[i]==s[j] dp[i-1][j-1]
//无论如何dp[i][j]+=dp[i][j-1]
//可以利用空串的性质去思考
for(int j=0;j<=n;++j) dp[0][j]=1;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
{
dp[i][j]+=dp[i][j-1];
if(t[i-1]==s[j-1]) dp[i][j]+=dp[i-1][j-1];
}
return dp[m][n];
}
};
四、通配符匹配(重点)
. - 力扣(LeetCode)
class Solution {
public:
bool isMatch(string s, string p)
{
//两个数组的dp问题
//p中0-j的子串能否匹配s中0-i的子串
int m=s.size(),n=p.size();
s=" "+s,p=" "+p;
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
//初始化第一行 当s为空(i=0时)
dp[0][0]=true;
for(int j=1;j<=n;++j)
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-1][j]||dp[i][j-1];
else dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1];
return dp[m][n];
}
};
五、正则表达式匹配(重点)
. - 力扣(LeetCode)
class Solution {
public:
bool isMatch(string s, string p) {
//p中0-j的子串能否匹配s中0-i的子串
int m=s.size(),n=p.size();
s=" "+s,p=" "+p;//控制下标的映射
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
//如果是 (p[j]=="."||p[j]==s[i])&&dp[i-1][j-1]
//如果是 * 取决于p[j-1] p[j-1]='.' 匹配空 dp[i][j-2] 匹配1个 dp[i-1][j-2]……
//所以dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-2][j-2]……
//数学推导 dp[i-1][j]=dp[i-1][j-2]||dp[i-2][j-2]……
//dp[i][j]=dp[i][j-2]||dp[i-1][j]
//如果p[j-1]==s[i]
//初始化
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]=(p[j]=='.'||p[j]==s[i])&&dp[i-1][j-1];
return dp[m][n];
}
};
六、交错字符串
. - 力扣(LeetCode)
预处理:在s1、s2、s3前面加上“ ”
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示:s1字符串的[1,i]区间和s2字符串的[1,j]区间的字符串能否拼凑成s3[1,i+j]子串
2、状态转移方程
dp[i][j]: (从最后一个位置)
dp[i][j]= s1[i]==s3[i+j]&&dp[i-1][j] ||s2[j]==s3[i+j]&&dp[i][j-1]
3、初始化
引入空串去思考:
当s1和s2均为空串时,s3也为空串,所以是true
当s1是空串,s2不是空串时,s3取决于s2 所以如果第一行一直是s2[j]==s3[j]就是true,一旦有一个不满足,就跳出循环。
当s2是空串,s1不是空串时,s3取决于s1 所以如果第一列一直是s1[i]==s3[i]就是true,一旦有一个不满足,就跳出循环。
所以需要按照上面的规则对第一行和第一列进行相关的初始化。
4、填表顺序
从上往下填每一行
每一行从左往右填
5、返回值
dp[m][n]
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m=s1.size(),n=s2.size();
if(m+n!=s3.size()) return false;//优化
s1=" "+s1,s2=" "+s2,s3=" "+s3;
//dp[i][j]表示s1 1-i s2 1-j 能否组成 s3 1-i+j
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
//先初始化第一列 此时s2是空串
dp[0][0]=true;
for(int i=1;i<=m;++i)
if(s1[i]==s3[i]) dp[i][0]=true;
else break;
//初始化第一行 s1是空串
for(int j=1;j<=n;++j)
if(s2[j]==s3[j]) dp[0][j]=true;
else break;
//开始填表 讨论最后一个位置 s1[i]==s[j]
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];
}
};
七、两个字符串的最小ASCII删除和
. - 力扣(LeetCode)
预处理:要求删除序列的最小ascii值,删除之后剩下的序列是一样的,并且总ascii值是不变的,所以我们可以运用正难则反的思路。
将问题转化为:求两个字符串所有最长公共子序列中的ascii码值的最大和
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示:s1字符串的[0,i]区间和s2字符串的[0,j]区间的所有子序列里,公共子序列最大的ascii码和
2、状态转移方程
dp[i][j]: (从最后一个位置)
s1[i]==s2[j]——dp[i-1][j-1]+s1[i]
s1[i]!=s2[j]——max(dp[i-1][j],dp[i][j-1])
3、初始化
引入空串去思考:
都初始化为0即可
4、填表顺序
从上往下填每一行
每一行从左往右填
5、返回值
sum-2*dp[m][n] (sum为两个字符串的ascii码值总和)
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m=s1.size(),n=s2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
//正难则反 找两个字符串的最小ascii删除和可以等价于
//找两个字符串的ascii总值-两个字符串的最长公共子序列的ascii值
//dp[i][j] s1 0-i 以及s2 0-j 所有子序列中最长公共子序列的ascii值总和
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];
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
int sum=0;
for(char&ch:s1) sum+=ch;
for(char&ch:s2) sum+=ch;
return sum-2*dp[m][n];
}
};
八、最长重复子数组
. - 力扣(LeetCode)
子数组最大的特点就是必须连续!!
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示:nums1中以i位置为结尾的所有子数组以及nums2中以j位置为结尾的所有子数组中,最长重复子数组的长度。
2、状态转移方程
dp[i][j]: (从最后一个位置)
nums1[i]!=nums2[j]——>0
nums1[i]==nums2[j]——>dp[i-1][j-1]+1
3、初始化
都初始化为0即可
4、填表顺序
从上往下填每一行
每一行从左往右填
5、返回值
dp表中的最大值
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(),n=nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
//dp[i][j]表示 nums1以i位置结尾 nums2以j位置结尾的最长公共子数组长度
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;
}
};