动态规划——两个数组的dp问题

目录

1. 最长公共子序列

2. 不相交的线

3. 不同的子序列 

4. 通配符匹配

5. 正则表达式匹配 

6. 交错字符串 

7. 两个字符串的最小ASCII删除和 

8. 最长重复子数组 

---

1. 最长公共子序列

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

题目展示：

题目分析：

这里说明一下，在做字符串类型的dp问题时，我们可以在原字符串的前面加上一个字符，这样下标的关系就不需要去调整了。 

代码实现：

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m=text1.size();int n=text2.size();//创建dp表vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化，让每个字符串加一个字符，解决下表映射问题text1=" "+text1;text2=" "+text2;//填表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];}
};

2. 不相交的线

题目链接：1035. 不相交的线 - 力扣（LeetCode）

题目展示：

题目分析：

本题和上一题解法一样，可以转化为上一道题。 

代码实现：

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size();int 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];}
};

3. 不同的子序列 

题目链接：115. 不同的子序列 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

class Solution {
public:int numDistinct(string s, string t) {int n=s.size();int m=t.size();vector<vector<double>> dp(m+1,vector<double>(n+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];}
};

4. 通配符匹配

题目链接：44. 通配符匹配 - 力扣（LeetCode）

题目展示：

题目分析：

笔误修正：s[i]==p[j] 

代码实现：

class Solution 
{
public:bool isMatch(string s, string p) {int m=s.size();int n=p.size();s=" "+s;p=" "+p;vector<vector<bool>> dp(m+1,vector<bool>(n+1));dp[0][0]=true;for(int i=1;i<=n;i++){if(p[i]=='*') dp[0][i]=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];}
};

5. 正则表达式匹配 

题目链接：10. 正则表达式匹配 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

class Solution {
public:bool isMatch(string s, string p) {int m=s.size();int n=p.size();vector<vector<bool>> dp(m+1,vector<bool>(n+1));s=" "+s;p=" "+p;dp[0][0]=true;for(int i=2;i<=n;i+=2){if(p[i]=='*') dp[0][i]=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]==s[i]||p[j]=='.')&&dp[i-1][j-1];}}return dp[m][n];}
};

6. 交错字符串 

题目链接：97. 交错字符串 - 力扣（LeetCode）

题目展示：

题目分析：

这里大家需要注意我们的预处理，前面加一个空串可以帮我们解决下标映射的问题。 

代码实现：

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m=s1.size();int 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 i=1;i<=n;i++){if(s2[i]==s3[i]) dp[0][i]=true;else break;}for(int j=1;j<=m;j++){if(s1[j]==s3[j]) dp[j][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];}
};

7. 两个字符串的最小ASCII删除和 

题目链接：712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m=s1.size();int n=s2.size();s1=" "+s1;s2=" "+s2;vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j]);if(s1[i]==s2[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i]);}}int ret=0;for(int i=1;i<=m;i++){ret+=s1[i];}for(int j=1;j<=n;j++){ret+=s2[j];}return ret-dp[m][n]*2;}
};

8. 最长重复子数组 

题目链接：718. 最长重复子数组 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size();int 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]=0;}}int ret=INT_MIN;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(dp[i][j]>ret) ret=dp[i][j];}}return ret;}
};