72.编辑距离,补充注释

linwt · linwt · commit 263e7694b747 · 2022-03-23T08:31:00.000+08:00
diff --git a/leetcode_Java/Solution0072.java b/leetcode_Java/Solution0072.java
@@ -4,7 +4,7 @@
 /*
 动态规划：自底向上
 1、题目：给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
-2、题目简化：字符串word1转换字符串word2的最少操作数
+2、题目简化：求字符串word1转换字符串word2的最少操作数
 3、定义dp数组：
   1）dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符使用的最少操作数
   2）扩增dp数组，int[][] dp = new int[n+1][m+1]，dp[0][0]表示两个都是空字符，首行首列表示至少其中一个字符串为空字符的情况
@@ -21,11 +21,17 @@
      ② 删除：若此时 word1 的 0~i-1 位置与 word2 的 0~j 位置已经匹配了，此时多出了 word1 的 i 位置字符，应把它删除掉两者才变得相同，因此 dp[i][j] = dp[i - 1][j] + 1;
      ③ 插入：若此时 word1 的 0~i 位置只是和 word2 的 0~j-1 位置匹配，此时只需要在 word1 的 i 位置后面插入一个和 word2 的 j 位置相同的字符，使得两者变得相同，因此 dp[i][j] = dp[i][j - 1] + 1;
      注：加1表示执行一次操作
-6、以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
+6、举例：以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
   1）dp[i-1][j-1] 表示替换操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将 word1 第五个字符替换成 word2 的第三个字符，即由 e 替换为 s
   2）dp[i][j-1] 表示删除操作，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾插入一个 s
   3）dp[i-1][j] 表示插入操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符
-7、遍历dp数组填表：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
+7、遍历dp数组填表：
+  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
+  2）外层遍历word1，内层遍历word2。
+    从二维数组角度看，顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
+    从两个字符串角度看，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
+  3）遍历顺序决定了哪些位置是计算过的、是已知状态
 8、返回结果：最后一个状态就是结果
 
    ''  r   o   s
@@ -35,6 +41,14 @@
 r  3   2   2   2
 s  4   3   3   2
 e  5   4   4   3
+
+       word1[i] == word2[j]     word1[i] != word2[j]
+word1：  h  r  o  s  e             h  r  o  s  e
+                  ↑                            ↑
+                  i                            i
+word2：  r  o  s                   r  o  s
+               ↑                         ↑
+               j                         j
  */
 class Solution {
     public int minDistance(String word1, String word2) {
diff --git a/leetcode_Java/Solution0115.java b/leetcode_Java/Solution0115.java
@@ -1,6 +1,9 @@
 // 115. 不同的子序列
 
 
+/*
+
+ */
 class Solution {
     public int numDistinct(String s, String t) {
         int n = s.length(), m = t.length();
