文章目录
- 最长公共子序列
- 不相交的线
- 不同的子序列
- 通配符匹配
最长公共子序列
题目：最长公共子序列
思路
选取
s1的[0, i]区间以及s2的[0， j]区间作为研究对象
-
状态表示：
dp[i][j]表示，s1的[0, i]区间以及s2的[0， j]区间内所有的子序列中，最长公共子序列的长度 -
状态转移方程：
s1[i] == s2[j]时，即最长公共子序列以s1[i]结尾，所以有dp[i][j] = dp[i - 1][j - 1] + 1s1[i] != s2[j]时，最长公共子序列一定不以s1[i]结尾，所以- 去
s1的[0, i - 1]区间以及s2的[0， j]区间寻找答案，即dp[i][j] = dp[i - 1][j] - 去
s1的[0, i]区间以及s2的[0，j - 1 ]区间寻找答案，即dp[i][j] = dp[i][j - 1] - 去
s1的[0, i - 1]区间以及s2的[0， j - 1]区间寻找答案，即dp[i][j] = dp[i - 1][j - 1]
- 综上，
1和2以及包括3，所以dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
- 去
-
初始化：引入空串，帮助我们初始化
在s1, s2前添加一个空字符，也就是说s1[0]和s2[0]的位置的值是空串;
dp表的大小为(m+1) x (n+1)，其中m和n是s1和s2的长度。初始化时，将第一行和第一列的值都设置为0
注意下标的映射 -
填表顺序：每次
i和j都需要用到i - 1和j - 1，所以从上往下填，从左往右填 -
返回值：
dp[m][n]，其中m和n是s1和s2的长度
C++代码
class Solution
{
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.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(text1[i - 1] == text2[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];}
};
不相交的线
题目：不相交的线
思路
阅读本题后发现和上题解法基本相同
C++代码
class Solution
{
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), 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;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);return dp[m][n];}
};
不同的子序列
题目：不同的子序列
思路
选取
t的[0, i]区间以及s的[0， j]区间作为研究对象
- 状态表示：
dp[i][j]表示，s的[0, j]区间内所有的子序列中，有多少个t的[0， i]区间内的子串 - 状态转移方程：根据
s的子序列包不包含s[j]来划分- 包含
s[j]时，t[i] == s[j]，此时dp[i][j] = dp[i - 1][j - 1] - 不包含
s[j]时，此时dp[i][j] = dp[i][j - 1]
- 包含
- 初始化：引入空串，注意下标的映射，
- 当
t为空时，s中至少有一个空串是其子串，所以第一行为1 - 当
s为空时，t只有是空串时，符合题意，第一列除了第一个都是0
- 当
- 填表顺序：
i和j填写都需要用到i - 1和j - 1，所以从上往下填，从左往右填 - 返回值：
dp[m][n]，其中m和n是t和s的长度
C++代码
class Solution
{
public:int numDistinct(string s, string t) {int m = t.size(), n = s.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];}
};
通配符匹配
题目：通配符匹配
思路
选取选取第一个字符串
[0, i]区间以及第二个字符串[0, j]区间作为研究对象
-
状态表示：
dp[i][j]表示，p的[0, j]区间内的子串中，能否匹配s的[0， i]区间内的子串 -
状态转移方程：根据根据最后一个位置的元素，来讨论
p[j]是普通字符，s[i] == p[j] && dp[i - 1][j - 1] == true ->truep[j] == '?'，dp[i - 1][j - 1] == true -> truep[j] == '*'- 匹配空串，
dp[i][j - 1] - 匹配一个字符
s[i]，dp[i - 1][j - 1] - 匹配两个字符
s[i]、s[i - 1]，dp[i - 2][j - 1] ... ... ... ...
优化
p[j] == '*'-
- 我们注意到
dp[i][j] = dp[i][j -2] || dp[i - 1][j - 2] || dp[i -2][j -2] || ... ...dp[i - 1][j] = dp[i - 1][j -2] || dp[i - 2][j - 2] || dp[i -3][j -2] || ... ...- 所以，
dp[i][j] = dp[i][j - 1] || dp[i - 1][j] -
- 匹配空串，
dp[i][j - 1] - 匹配一个，但不舍去
*，dp[i - 1][j] - 所以，
dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
- 匹配空串，
-
初始化：引入空串，注意下标的映射，
- 初始化整个数组为
false dp[0][0]表示两个空串是否匹配，初始化为true- 第一行表示
s为空串，p串与空串只有一种匹配可能，即 p 串表示为"***"，此时也相当于空串匹配上空串，将所有前导为"*"的p子串与空串的dp值设为true
- 初始化整个数组为
-
填表顺序：
i和j填写都需要用到i - 1和j - 1，所以从上往下填，从左往右填 -
返回值：
dp[m][n]，其中m和n是s和p的长度
C++代码
class Solution
{
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));s = " " + s;p = " " + p;dp[0][0] = true;for(int j = 1; j <= n; j++)if(p[j] == '*') dp[0][j] = 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];elsedp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i -1][j - 1];}return dp[m][n];}
};
