- 最长公共子序列
状态表示:
选取第一个字符串[0,i]区间和第二个字符串[0,j]区间作为研究对象
dp[i][j]: 表示s1的[0,i]区间和s2的[0,j]区间内的所有子序列中,最长公共子序列的长度
状态转移方程:
text1[i] == text2[j]:
dp[i][j] = dp[i-1][j-1] + 1;
text1[i] != text2[j]:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
int longestCommonSubsequence(string text1, string text2)
{
// 1.dp数组
vector<vector<int>> dp(text1.size(), vector<int>(text2.size()));
// 2.初始化
if(text1[0] == text2[0]) dp[0][0] = 1;
for(int i = 1; i < text1.size(); ++i)
{
if(text1[i] == text2[0]) dp[i][0] = 1;
else dp[i][0] = dp[i-1][0];
}
for(int j = 1; j < text2.size(); ++j)
{
if(text2[j] == text1[0]) dp[0][j] = 1;
else dp[0][j] = dp[0][j-1];
}
// 3.状态转移方程
for(int i = 1; i < text1.size(); ++i)
{
for(int j = 1; j < text2.size(); ++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]);
}
}
// 4.返回值
return dp.back().back();
}
- 不相交的线
状态表示 & 状态转移方程: 参考1.最长公共子序列
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2)
{
// 1.dp数组
vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size()));
// 2.初始化
if(nums1[0] == nums2[0]) dp[0][0] = 1;
for(int i = 1; i < nums1.size(); ++i)
{
if(nums1[i] == nums2[0]) dp[i][0] = 1;
else dp[i][0] = dp[i-1][0];
}
for(int j = 1; j < nums2.size(); ++j)
{
if(nums2[j] == nums1[0]) dp[0][j] = 1;
else dp[0][j] = dp[0][j-1];
}
// 3.状态转移方程
for(int i = 1; i < nums1.size(); ++i)
{
for(int j = 1; j < nums2.size(); ++j)
{
if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
// 4.返回值
return dp.back().back();
}
- 不同的子序列
状态表示:
dp[i][j]: 表示 s 字符串 [0, i] 区间内的所有子序列中,有多少个 t 字符串 [0, j] 区间子串
状态转移方程:
s[i] == t[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
s[i] != t[j]: dp[i][j] = dp[i-1][j]
int numDistinct(string s, string t)
{
// 1.dp数组
vector<vector<unsigned int>> dp(s.size(), vector<unsigned int>(t.size()));
// 2.初始化
if(s[0] == t[0]) dp[0][0] = 1;
for(int i = 1; i < s.size(); ++i)
{
if(s[i] == t[0]) dp[i][0] = dp[i-1][0] + 1;
else dp[i][0] = dp[i-1][0];
}
// 3.状态转移方程
for(int i = 1; i < s.size(); ++i)
{
for(int j = 1; j < t.size(); ++j)
{
if(s[i] == t[j]) dp[i][j] += dp[i-1][j-1];
dp[i][j] += dp[i-1][j];
}
}
// 4.返回值
return dp.back().back();
}
- 通配符匹配
状态表示:
dp[i][j]: 表示字符模式p的[0,j]区间子串,能否匹配字符串s的[0,i]区间子串
状态转移方程:
p最后一个字符是英文字符:
dp[i][j] = p[j] == s[i] && dp[i-1][j-1]
p最后一个字符是'?':
dp[i][j] = dp[i-1][j-1]
p最后一个字符是'*':
dp[i][j] = dp[i-1][j] || dp[i][j-1]
bool isMatch(string s, string p)
{
// 1.dp数组
vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
// 2.初始化
// p[0] - ""
dp[0][0] = true;
// s[0] = ""
for(int j = 1; j <= p.size(); ++j)
{
if(p[j-1] == '*') dp[0][j] = true;
else break;
}
// 3.状态转移方程
for(int i = 1; i <= s.size(); ++i)
{
for(int j = 1; j <= p.size(); ++j)
{
if(isalpha(p[j-1]))
{
if(p[j-1] == s[i-1] && dp[i-1][j-1]) dp[i][j] = true;
}
else if(p[j-1] == '?')
{
if(dp[i-1][j-1]) dp[i][j] = true;
}
else
{
// 方式一
dp[i][j] = dp[i-1][j] || dp[i][j-1];
// 方式二
// for(int k = 0; k <= i; ++k)
// {
// if(dp[k][j-1])
// {
// dp[i][j] = true;
// break;
// }
// }
}
}
}
// 4.返回值
return dp.back().back();
}
- 正则表达式匹配
状态表示:
dp[i][j]: 表示字符规律p的[0,j]区间子串,能否匹配字符串s的[0,i]区间子串
bool isMatch(string s, string p)
{
// 0.预处理
s = " " + s;
p = " " + p;
// 1.dp数组
vector<vector<bool>> dp(s.size(), vector<bool>(p.size(), false));
// 2.初始化
// p[0]
dp[0][0] = true;
// s[0]
for(int j = 2; j < dp[0].size(); j += 2)
{
if(p[j] == '*') dp[0][j] = true;
else break;
}
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++i)
{
for(int j = 1; j < dp[0].size(); ++j)
{
if(isalpha(p[j]))
{
if(p[j] == s[i] && dp[i-1][j-1]) dp[i][j] = true;
}
else if(p[j] == '.')
{
if(dp[i-1][j-1]) dp[i][j] = true;
}
else
{
if(p[j-1] == '.')
{
dp[i][j] = dp[i][j-2] || dp[i-1][j];
}
else
{
dp[i][j] = dp[i][j-2] || (p[j-1] == s[i] && dp[i-1][j]);
}
}
}
}
// 4.返回值
return dp.back().back();
}
- 交错字符串
状态表示:
dp[i][j]: 表示s1中[1,i]区间子串和s2中[1,j]区间子串能否拼凑成s3中[1,i+j]区间子串
bool isInterleave(string s1, string s2, string s3)
{
// 0.预处理
if(s3.size() != s1.size() + s2.size()) return false;
s1 = " " + s1;
s2 = " " + s2;
s3 = " " + s3;
// 1.dp数组
vector<vector<bool>> dp(s1.size(), vector<bool>(s2.size()));
// 2.初始化
dp[0][0] = true;
for(int j = 1; j < dp[0].size(); ++j)
{
if(s2[j] == s3[j]) dp[0][j] = true;
else break;
}
for(int i = 1; i < dp.size(); ++i)
{
if(s1[i] == s3[i]) dp[i][0] = true;
else break;
}
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++i)
{
for(int j = 1; j < dp[0].size(); ++j)
{
if((s1[i] == s3[i+j] && dp[i-1][j])
|| (s2[j] == s3[i+j] && dp[i][j-1]))
dp[i][j] = true;
}
}
// 4.返回值
return dp.back().back();
}
- 两个字符串的最小ASCII删除和
问题转化:
求两个字符串所有公共子序列的ASCII码值最大和
状态表示:
dp[i][j]: 表示s1的[0,i]区间和s2的[0,j]区间内的所有子序列中,公共子序列的ASCII码值最大和
int minimumDeleteSum(string s1, string s2)
{
// 0.预处理
int sum = 0;
for(char c : s1) sum += c;
for(char c : s2) sum += c;
s1 = " " + s1;
s2 = " " + s2;
// 1.dp数组
vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));
// 2.初始化
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++i)
{
for(int j = 1; j < dp[0].size(); ++j)
{
if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + s1[i];
if(dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j];
if(dp[i][j-1] > dp[i][j]) dp[i][j] = dp[i][j-1];
}
}
// 4.返回值
return sum - 2 * dp.back().back();
}
- 最长重复子数组
状态表示:
dp[i][j]: 表示num1中以i位置元素为结尾的所有子数组和num2中以j位置元素为结尾的所有子数组中,最长重复子数组的长度
int findLength(vector<int>& nums1, vector<int>& nums2)
{
// 1.dp数组
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));
// 2.初始化
// 3.状态转移方程
int ret = 0;
for(int i = 1; i < dp.size(); ++i)
{
for(int j = 1; j < dp[0].size(); ++j)
{
if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
ret = max(ret, dp[i][j]);
}
}
// 4.返回值
return ret;
}