动态规划——两个数组的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;
else
dp[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;
else
break;
}
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];
else
dp[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;
else
break;
}
for(int i = 1; i <= m; i++)
{
if(s1[i] == s3[i])
dp[i][0] = true;
else
break;
}
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];
}
}; 