Day45--动态规划--115. 不同的子序列，583. 两个字符串的删除操作，72. 编辑距离

这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用KMP。

思路：

1. dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2. 递推公式：
   • 当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
     • 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i - 1][j - 1]。
     • 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
   • 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
3. 初始化：dp[i][0]一定都是1
4. 遍历顺序：从上到下，从左到右

class Solution {public int numDistinct(String s, String t) {// 长串int n1 = s.length();// 子系列串int n2 = t.length();int[][] dp = new int[n1 + 1][n2 + 1];// 初始化for (int i = 0; i < n1; i++) {dp[i][0] = 1;}// 动态规划for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j];}}}return dp[n1][n2];}
}

好难，有点绕晕了。回头再重做。

思路：

1. dp[i][j]含义：最少删除次数
2. 递推公式：
   • 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
   • 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
     • 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
     • 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
     • 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
     • 特别的，情况三可以与情况一或二合并。举例与情况二合并：当你同时删word1[i - 1]和word2[j - 1]的时候，可以等于dp[i][j - 1] + 1，因为dp[i][j - 1]本来就不要了word1[i-1]了
     • 因此，递推公式为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
3. 初始化：可以想象当另一个字符串是空串的时候，本串第i位就要删i个元素，才可以和空串相等
   • for (int i = 0; i < n1; i++)dp[i][0] = i;
   • for (int j = 0; j < n2; j++)dp[0][j] = j;
4. 遍历顺序：从上到下，从左到右

class Solution {public int minDistance(String word1, String word2) {int n1 = word1.length();int n2 = word2.length();int[][] dp = new int[n1 + 1][n2 + 1];// 初始化（可以想象当另一个字符串是空串的时候，本串第i位就要删i个元素，才可以和空串相等）for (int i = 0; i <= n1; i++) {dp[i][0] = i;}for (int j = 0; j <= n2; j++) {dp[0][j] = j;}// 动态规划for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {// 不用删dp[i][j] = dp[i - 1][j - 1];} else {// 删，取小值dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[n1][n2];}
}

思路：

没想到吧，1143. 最长公共子序列又来了。

求最长公共子序列。然后大家都减去公共部分，剩下的就是不同的部分的长度了（要删的长度）

class Solution {public int minDistance(String word1, String word2) {int n1 = word1.length();int n2 = word2.length();int[][] dp = new int[n1 + 1][n2 + 1];int maxLen = 0;for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}if (dp[i][j] > maxLen) {maxLen = dp[i][j];}}}// 求最长公共子序列。然后大家都减去公共部分，剩下的就是不同的部分的长度了（要删的长度）return n1 + n2 - 2 * maxLen;}
}

思路：

1. dp含义：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

2. 递推公式：

   • 情况一：if (word1[i - 1] == word2[j - 1])，不操作。dp[i][j] = dp[i - 1][j - 1]
   • 情况二：if (word1[i - 1] != word2[j - 1])增删换
     • 增加和删除是同样的公式的，这边增加一个，等于那边删除一个。我们按熟悉的删除来：如果有一边多，就删掉一个元素：Math.min(dp[i][j] = dp[i - 1][j] + 1,dp[i][j] = dp[i][j - 1] + 1);
     • 换是什么意思？
       • 回忆一下情况一：如果if (word1[i - 1] == word2[j - 1])，相等，我们就dp[i][j] = dp[i - 1][j - 1]。
       • 假设word1替换word1[i - 1]，使其与word2[j - 1]相同。那不就是dp[i][j] = dp[i - 1][j - 1] + 1就行了吗？——只要“换一次”就相同。那就是在未相同的情况上，加一次操作，就等于相同。
     • 综上：情况二：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

3. 初始化：

   • 那么dp[i][0] 和 dp[0][j] 表示什么呢？——要操作多少步才能使对方变成空串。

   • 所以：

     for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
     for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
     

4. 遍历顺序：dp[i][j]与[i-1]和[j-1]都有关系，所以要从上到下，从左到右遍历。

class Solution {public int minDistance(String word1, String word2) {int n1 = word1.length();int n2 = word2.length();char[] ch1 = word1.toCharArray();char[] ch2 = word2.toCharArray();int[][] dp = new int[n1 + 1][n2 + 1];// 初始化for (int i = 1; i <= n1; i++) {dp[i][0] = i;}for (int j = 1; j <= n2; j++) {dp[0][j] = j;}for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (ch1[i - 1] == ch2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}}}return dp[n1][n2];}
}

记录，这道题也是比较晕的。回头要重做。