【dp】不同的子序列 两个字符串的删除操作 编辑距离

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，想要达到相等，所需要删除元素的最少次数

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. 编辑距离

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];}
};