目录
题四十 最长公共子序列
题解:
状态方程:dp[i][j]:表示s1字符串[0,i]区间和s2字符串[0,j]区间,最长公共子序列。
根据方程进行推导:分两种情况讨论当s1[i] == s2[j] / s1[i] != s2[j]
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//1、创建dp表
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1));
//2、初始化
text1 = " " + text1;
text2 = " " + text2;
//3、填表
for(int i = 1; i<n+1; ++i)
{
for(int j = 1; j<m+1; ++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[n][m];
}
};
题四十一 不相交的线
题解:
状态方程:dp[i][j]:nums1序列[0,i]区间和nums2序列[0,j]区间,有多少个不相交线。
根据方程进行推导:分两种情况讨论当s1[i] == s2[j] / s1[i] != s2[j]
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//1、创建dp表
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> dp(m+1, vector<int> (n+1));
//2、初始化
//3、填表
for(int i = 1; i<m+1; ++i)
{
for(int j = 1; j<n+1; ++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]);
}
}
}
//4、返回值
return dp[m][n];
}
};
题四十二 不同子序列
LCR 097. 不同的子序列 - 力扣(LeetCode)
题解:
dp[i][j]:表示[0,i]区间的s串,有多少个[0,j]区间的t串。
根据此状态方程推导。
class Solution {
public:
int numDistinct(string s, string t) {
//1、创建dp表
int m = s.size();
int n = t. size();
vector<vector<double>> dp(m+1, vector<double> (n+1));
//2、初始化
for(int i = 0; i<m+1; ++i)
{
dp[i][0] = 1;
}
//3、填表
for(int i = 1; i<m+1; ++i)
{
for(int j = 1; j<n+1; ++j)
{
dp[i][j] += dp[i-1][j];
if(s[i-1] == t[j-1])
{
dp[i][j] += dp[i-1][j-1];
}
}
}
//4、返回值
return dp[m][n];
}
};
题四十三 通配符匹配
题解:
dp[i][j]:表示[0,i]区间的s串,有多少个[0,j]区间的t串。
根据此状态方程推导。