115. 不同的子序列
- dp[i][j]：以j-1为结尾的t出现在以i-1为结尾的s子序列的个数
需要开辟m+1行，n+1列的二维数组
为啥状态方程是：
-
s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
-
s[i] != t[j] 时 dp[i][j] = dp[i-1][j]
先看s[i] == t[j] 时，以s = “rara” t = “ra” 为例，当i = 3, j = 1时，s[i] == t[j]
此时分为2种情况：s串用最后一位的a 以及 不用最后一位的a
-
如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
-
如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
再看s[i] != t[j] 比如 s = “rarb” t = “ra” 还是当i = 3, j = 1时，s[i] != t[j]
此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
所以此时dp[i][j] = dp[i-1][j]
如果当前字符s[i - 1]和 t[i - 1]相等，则可以使用当前字符匹配，并使用s[0]~s[i - 2]匹配t[0]~t[j - 2]，即dp[i - 1][j - 1]。还可以不使用当前字符s[i - 1]匹配，使用s[0]~s[i - 2]匹配t[0]~t[j - 1]，即dp[i - 1][j]
如果当前字符s[i - 1]和 t[i - 1]不相等，则不能使用当前字符s[i - 1]匹配，需要使用s[0]~s[i-2]匹配t[0]~t[j-1]，即dp[i-1][j]
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size();
int n = t.size();
// dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数
vector<vector<uint64_t>> dp(m + 1, vector<uint64_t>(n + 1));
// 空字符串出现在空字符串的次数
dp[0][0] = 1;
// t为空，空字符串出现在s中的次数
for (int i = 1; i <= m; i++) dp[i][0] = 1;
// s为空，t出现在空字符串中的次数
for (int j = 1; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1]) {
// 当前字符相等
// 用当前字符匹配，即使用s[0 ~ i-2]匹配t[0 ~ j-2] dp[i - 1][j - 1]
// 不用当前字符匹配，即使用s[0 ~ i-2]匹配t[0 ~ j-1] dp[i - 1][j]
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// 不用当前字符匹配，即使用s[0 ~ i-2]匹配t[0 ~ j-1] dp[i - 1][j]
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
};
583. 两个字符串的删除操作
- dp[i][j]：以i-1为结尾的字符串word1，和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
文章来源：https://www.toymoban.com/news/detail-413667.html
class Solution {
public:
int minDistance(string word1, string word2) {
// dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
// dp[i][j] = dp[i - 1][j - 1];
// dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
dp[0][0] = 0; // word1、word2都为空串，删除0次相同
for(int i = 1; i <= m; i++) dp[i][0] = i; // word2为空串，word1[0~i-1]变成空串，需要删除i次
for(int j = 1; j <= n; j++) dp[0][j] = j; // word1为空串，word2[0~j-1]变成空串，需要删除j次
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i - 1] == word2[j - 1]){
// 如果当前字符相等，则当前字符不用删除，word1[0] ~ word1[i - 1]和word2[0] ~ word2[j - 1]删除dp[i][j]次后相同
// 与word1[0] ~ word1[i - 12]和word2[0] ~ word2[j - 2]删除dp[i - 1][j - 1]次后相同
// 这两个删除次数应该相同
dp[i][j] = dp[i - 1][j - 1];
}else{
// 若当前字符不相同，则要么是当前的两个字符都删除，变成word1[0] ~ word1[i - 2]和word2[0] ~ word2[j - 2]
// 要么是删除word1[i - 1]，要么是word2[j - 1]
// 三个取最小值即可
dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
}
}
}
return dp[m][n];
}
};
72. 编辑距离
文章来源地址https://www.toymoban.com/news/detail-413667.html
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
dp[0][0] = 0;
for(int i = 1; i <= m; i++) dp[i][0] = i;
for(int j = 1; j <= n; j++) dp[0][j] = j;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
}
}
return dp[m][n];
}
};
到了这里，关于【dp】不同的子序列 & 两个字符串的删除操作 & 编辑距离的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
