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

目录

一、最长公共子序列

二、不同的子序列

三、通配符匹配

四、正则表达式匹配

五、两个字符串的最小ASCII删除和

六、最长重复子数组

七、交错字符串

---

一、最长公共子序列

最长公共子序列

第一步：确定状态表示

dp[i][j]：表示字符串 s1 的 [0，i] 区间以及字符串 s2 的[0，j] 区间内所有子序列中，最长公共子序列的长度。

第二步：推出状态转移方程

第三步：初始化dp表

关于字符串的 dp 问题，我们需要考虑空串的情况，比如 s1 选一个空串，s2 选一个空串，其实也属于是一个公共子序列，不过公共子序列长度为0。

我们可以在原始 dp 表上多加一行一列，第0行表示第一个字符串为空，第0列表示第二个字符串为空。

让dp表多加了一行和一列后，我们需要注意dp表的下标和字符串下标的对应关系。 

解题代码：

class Solution 
{
public:int longestCommonSubsequence(string s1, string s2) {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] + 1;elsedp[i][j] = max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));}}return dp[m][n];}
};

 

---

二、不同的子序列

不同的子序列

第一步：确定状态表示

dp[i][j]：表示s字符串 [0，i]区间内所有子序列中，有多少个t字符串 [0，j] 区间内的子串。

第二步：推出状态转移方程

第三步：初始化dp表。

我们需要考虑空串的情况，比如 s1 选一个空串，s2 选一个空串，其实也属于是一个公共子序列。

第一行表示 s 字符串为空串，s 如果是空串，t 只有是空串，才能在 s 中找到 t。第一列表示 t 字符串为空串，t 如果是空串，s 不管是什么字符串，它里面都有一个空串。因此第一列应该全都是1。

解题代码：

class Solution 
{
public:int numDistinct(string s, string t){int m = s.size(), n = t.size();vector<vector<double>> dp(m+1, vector<double>(n+1));for(int i = 0; i <= m; i++)dp[i][0] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] += dp[i-1][j];if(s[i-1] == t[j-1])dp[i][j] += dp[i-1][j-1];}}return dp[m][n];}
};

 

---

三、通配符匹配

通配符匹配

第一步： 确定状态表示

dp[i][j]：表示p[0，i] 区间内的子串能否匹配 s[0，j] 区间内的子串。

第二步：推出状态转移方程

第三步：初始化dp表

如果s是空字符串，p字符串前面出现 ’ * ‘ 可以匹配空串，但是 ’ * ‘ 之后如果出现其他字符了，后面不管有多少个’ * '都不能匹配了。

dp[i][j]表示p[0，i] 区间内的子串能否匹配 s[0，j] 区间内的子串。题目要求是整个字符串，因此返回dp[m][n]，m是s的长度，n是p的长度。

解题代码：

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

 

---

四、正则表达式匹配

正则表达式匹配

第一步：确定状态表示

dp[i][j]：表示 p[0，i] 区间内的子串能否匹配 s[0，j] 区间内的字符串。

第二步：推出状态转移方程

第三步：初始化dp表

dp表上面多加一行表示p是空串，左边多加一列表示s是空串。接下来看看里面值应该填什么。

对于第一行，如果p是空串，s也是空串，肯定能匹配，所以第一行第一个空格还是true。

后续如果 p 是空串，s不是空串，肯定匹配不上，所以第一行后续都是false。

解题代码：

class Solution 
{
public:bool isMatch(string s, string p) {int m = p.size(), n = s.size();vector<vector<bool>> dp(m+1, vector<bool>(n+1));dp[0][0] = true;s = ' ' + s;p = ' ' + p;for(int i = 2; i <= m; i++){if(p[i] != '*' && p[i-1] != '*')break;if(p[i] == '*' && p[i-1] != '*')dp[i][0] = true;}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(p[i] >= 'a' && p[i] <= 'z'){if(p[i] == s[j] && dp[i-1][j-1] == true)dp[i][j] = true;}else if(p[i] == '.')dp[i][j] = dp[i-1][j-1];else{if(p[i-1] == '.')dp[i][j] = dp[i-2][j] || dp[i][j-1];elsedp[i][j] = dp[i-2][j] || (s[j] == p[i-1] && dp[i][j-1]);}}}return dp[m][n];}
};

 

---

五、两个字符串的最小ASCII删除和

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

预处理：本道题是让我们找使两个字符串相等，所需删除字符的ASCII值最小。而最开始的两个字符串的ASCII值总和是不变的，那么我们只需要找到两个字符串相同后，其ASCII值最大，那么删除的字符的ASCII值一定就是最小的。

所以说，该问题就转化成了：求两个字符串的所有公共子序列里面，ASCII值的最大和。

第一步：确定状态表示

dp[i][j]：表示字符串 s1 的 [0，i] 区间以及字符串 s2 的 [0，j] 区间内的所有公共子序列中， ASCII值最大和。

第二步：推出状态转移方程

对于s1[0，i]区间和s2[0，j]区间的公共子序列有四种情况，即：

有s1[i]，有s2[j]

有s1[i]，没有s2[j]

没有s1[i]，有s2[j]

没有s1[i]，没有s2[j]

情况四可以包含在情况二中。

第三步：初始化dp表

第四步：确定返回值

状态表示求的是两个字符串的区间里面公共子序列的ASCII值最大和。

而题目要求使两个字符串相等所需删除字符的ASCII值的最小和 。所以可以这样做：

1、找到两个字符串中公共子序列的Ascll 最大和，dp[m][n]。

2、统计两个字符串中ASCII值总和，sum。

3、sum - dp[m][n] * 2。

解题代码：

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));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][j-1], dp[i-1][j]));}}int sum = 0;for(auto x : s1)sum += x;for(auto x : s2)sum += x;return sum - 2 * dp[m][n];}
};

 

---

六、最长重复子数组

最长重复子数组

第一步：确定状态表示

dp[i][j]：表示数组 nums1 中以 i 位置元素为结尾的所有的子数组以及数组 nums2 中以 j 位置元素为结尾的所有子数组中，最长公共子数组的长度。

第二步：推出状态转移方程

第三步：初始化dp表

填写顺序：根据状态转移方程。从上往下填写每一行。 最后的返回值是 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));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;}
};

---

七、交错字符串

交错字符串

预处理：为了下标对应，我们给每个字符串的前面都加上一个空格字符。 

第一步：确定状态表示

dp[i][j]：表示s1[1，i]区间内的字符串和s2[1，j]区间内的字符串能不能拼成s3[1，i+j]区间内的字符串。

第二步：推出状态转移方程

第三步：初始化dp表

解题代码：

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;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;elsebreak;}for(int i = 1; i <= m; i++){if(s1[i] == s3[i])dp[i][0] = true;elsebreak;}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(s1[i] == s3[i+j] && dp[i-1][j])dp[i][j] = true;else if(s2[j] == s3[i+j] && dp[i][j-1])dp[i][j] = true;}}return dp[m][n];}
};