字符串的动态规划系列,补充注释

linwt · linwt · commit ba8d6412e54c · 2022-03-24T22:42:29.000+08:00
diff --git a/leetcode_Java/Solution0005.java b/leetcode_Java/Solution0005.java
@@ -85,15 +85,18 @@ private int expandAroudCenter(String s, int l, int r) {
 
 
 /*
+与“647.回文子串”相似
 动态规划：动态规划是暴力破解的优化，两者同样需要遍历列举判断所有子串是否为回文串，区别是暴力破解每次都要对子串单独处理判断是否为回文串，动态规划可以利用之前记录的子串结果直接判断当前子串是否为回文串
 1、题目：给你一个字符串 s，找到 s 中最长的回文子串。
 2、题目简化：求字符串s的最长回文子串。要先判断子串是否为回文串，再从回文子串中取最长。
 3、定义dp数组：dp[l][r]表示子串s[l,r]是否为回文子串，l是左区间，r是右区间
-4、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
+4、初始化：
+  1）二维dp数组不用扩容，直接根据dp数组的定义就可以直观地对应进行初始化
+  2）boolean数组创建时，默认值是false，只需要标记为true的地方即可。可以初始化dp数组 dp[i][i] = true，表示1个字符是回文
+5、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
    1）s[l] == s[r] 表示首尾两个字符相等
-   2）r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组的对角线为true
+   2）r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组单个字符为true
    3）dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
-5、初始化：boolean数组创建时，默认值是false，只需要标记为true的地方即可。可以初始化dp数组的对角线为true，即dp[i][i] = true，表示1个字符是回文
 6、遍历dp数组填表：一个for遍历子串的右区间，另一个for循环遍历子串的左区间，根据状态转移方程推断计算未知结果并填表，当是回文串时比较并记录最长长度和左右区间位置
 7、返回结果：根据遍历时记录的最长回文子串左右区间位置，截取字符串s得到最长回文子串
 
@@ -103,13 +106,13 @@ private int expandAroudCenter(String s, int l, int r) {
  */
 class Solution {
     public String longestPalindrome(String s) {
-        int len = s.length();
-        if (len < 2) {
+        int n = s.length();
+        if (n < 2) {
             return s;
         }
         int maxLen = 1, start = 0, end = 0;
-        boolean[][] dp = new boolean[len][len];
-        for (int r = 1; r < len; r++) {
+        boolean[][] dp = new boolean[n][n];
+        for (int r = 1; r < n; r++) {
             for (int l = 0; l < r; l++) {
                 if (s.charAt(l) == s.charAt(r) && (r - l < 3 || dp[l + 1][r - 1])) {
                     dp[l][r] = true;
diff --git a/leetcode_Java/Solution0583.java b/leetcode_Java/Solution0583.java
@@ -1,6 +1,48 @@
 // 583. 两个字符串的删除操作
 
 
+/*
+动态规划：
+1、题目简化：求使word1和word2相同的最少删除次数
+2、定义dp数组：dp[i][j] 表示使 word1前i个字符 和 word2前j个字符 相同的最少删除次数
+3、初始化：
+  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
+  2）dp[i][0] = i 表示使 word1前i个字符 和 空字符串 相同的最少删除次数为i
+     dp[0][j] = j 表示使 空字符 和 word2前j个字符 相同的最少删除次数为j
+4、状态转移方程：
+  1）如果word1[i] == word2[j]，即两个字符串最后一个字符相同，那么不用删除，结果为 word1前i-1个字符 和 word2前j-1个字符 相同的最少删除次数，即 dp[i][j] = dp[i - 1][j - 1];
+  2）如果word1[i] != word2[j]，即两个字符串最后一个字符不相同，那么需要一次删除操作，使用之前状态的最少删除次数加1，有两种情况是状态已知且字符最多的
+    ① 删除word1[i]，即 word1前i-1个字符 和 word2前j个字符 相同的最少删除次数 加1，即 dp[i - 1][j] + 1
+    ② 删除word2[j]，即 word1前i个字符 和 word2前j-1个字符 相同的最少删除次数 加1，即 dp[i][j - 1] + 1
+    比较这两种情况是因为删除的字符可能是相同的字符，会增加额外的删除操作，两者取最少就得到当前结果，即 dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
+5、遍历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] 都是已知状态了
+6、返回结果：最后一个状态就是结果
+
+word1 = "leetcode", word2 = "letgo", minDistance = 5
+   '' l  e  t  g  o
+'' 0  1  2  3  4  5
+l  1  0  1  2  3  4
+e  2  1  0  1  2  3
+e  3  2  1  2  3  4
+t  4  3  2  1  2  3
+c  5  4  3  2  3  4
+o  6  5  4  3  4  3
+d  7  6  5  4  5  4
+e  8  7  6  5  6  5
+
+        word1[i] == word2[j]          word1[i] != word2[j]
+word1:  l  e  e  t  c  o  d  e       l  e  e  t  c  o  d  e
+                 ↑                               ↑
+                 i                               i
+word2:  l  e  t  g  o                l  e  t  g  o
+              ↑                            ↑
+              j                            j
+ */
 class Solution {
     public int minDistance(String word1, String word2) {
         int n = word1.length(), m = word2.length();
@@ -22,4 +64,25 @@ public int minDistance(String word1, String word2) {
         }
         return dp[n][m];
     }
+}
+
+
+/*
+问题转化成“1143.最长公共子序列”，两个字符串除了公共部分，剩余的字符就是要删除的次数
+ */
+class Solution {
+    public int minDistance(String word1, String word2) {
+        int n = word1.length(), m = word2.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; 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]);
+                }
+            }
+        }
+        return n + m - 2 * dp[n][m];
+    }
 }
diff --git a/leetcode_Java/Solution0647.java b/leetcode_Java/Solution0647.java
@@ -2,7 +2,21 @@
 
 
 /*
-与“5.最长回文子串”相似
+与“5.最长回文子串”相似。本题是判断子串为回文串则数目加1
+动态规划：
+1、问题简化：求字符串s中回文子串的数目
+2、定义dp数组：dp[l][r]表示子串s[l,r]是否为回文子串，l是左区间，r是右区间
+3、初始化：
+  1）二维dp数组不用扩容，直接根据dp数组的定义就可以直观地对应进行初始化
+  2）boolean数组创建时，默认值是false，只需要标记为true的地方即可。可以初始化dp数组 dp[i][i] = true，表示1个字符是回文
+4、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
+   1）s[l] == s[r] 表示首尾两个字符相等
+   2）r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组单个字符为true
+   3）dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
+5、遍历dp数组填表：一个for遍历子串的右区间，另一个for循环遍历子串的左区间，顺序都是从左到右，根据状态转移方程推断计算未知结果并填表
+6、返回结果：
+  1）初始数目为字符串长度，即每个字符都是一个回文串
+  2）遍历时是回文串时累加记录回文串数目，最后返回结果
  */
 class Solution {
     public int countSubstrings(String s) {
diff --git a/leetcode_Java/Solution0712.java b/leetcode_Java/Solution0712.java
@@ -1,6 +1,45 @@
 // 712. 两个字符串的最小ASCII删除和
 
 
+/*
+动态规划：
+1、题目简化：求使s1和s2相同的最小ASCII删除和
+2、定义dp数组：dp[i][j] 表示使 s1前i个字符 和 s2前j个字符 相同的最小ASCII删除和
+3、初始化：
+  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
+  2）dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); 表示使 s1前i个字符 和 空字符串 相同的最小ASCII删除和，逐个累加
+    dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); 表示使 空字符串 和 s2前j个字符 相同的最小ASCII删除和，逐个累加
+4、状态转移方程：
+  1）如果s1[i] == s[j]，即两个字符串最后一个字符相同，那么不用删除，结果为 s1前i-1个字符 和 s2前j-1个字符 相同的最小ASCII删除和，即 dp[i][j] = dp[i - 1][j - 1];
+  1）如果s1[i] != s[j]，即两个字符串最后一个字符不相同，那么需要删除，使用之前状态的最小ASCII删除和 加上 当前被删除字符的ASCII值，有两种情况是状态已知且字符最多的
+    ① 删除s1[i]，即 s1前i-1个字符 和 s2前j个字符 相同的最小ASCII删除和 加上 当前被删除字符的ASCII值，即 dp[i - 1][j] + s1.charAt(i - 1)
+    ① 删除s2[j]，即 s1前i个字符 和 s2前j-1个字符 相同的最小ASCII删除和 加上 当前被删除字符的ASCII值，即 dp[i][j - 1] + s2.charAt(j - 1)
+    比较这两种情况是因为删除的字符可能是相同的字符，会增加额外的删除操作，两者取最少就得到当前结果，即 dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
+5、遍历dp数组填表
+  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最小ASCII删除和
+  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串s1，内层遍历字符串s2。
+    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
+    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
+6、返回结果：最后一个状态就是结果
+
+s1 = "delete", s2 = "leet"
+   ''    l    e    e    t
+''  0   108  209  310  426
+d  100  208  309  410  526
+e  201  309  208  309  425
+l  309  201  302  403  519
+e  410  302  201  302  418
+t  526  418  317  418  302
+e  627  519  418  317  403
+
+s1: d  e  l  e  t  e
+             ↑
+             i
+s2: l  e  e  t
+          ↑
+          j
+ */
 class Solution {
     public int minimumDeleteSum(String s1, String s2) {
         int n = s1.length(), m = s2.length();
diff --git a/leetcode_Java/Solution0718.java b/leetcode_Java/Solution0718.java
@@ -1,10 +1,43 @@
 // 718. 最长重复子数组
 
 
+/*
+动态规划：
+1、题目简化：求数组nums1和nums2中最长公共子数组的长度。注意子数组是连续的。（也可以理解成 求两个字符串的最长公共连续子串的长度）
+2、定义dp数组：dp[i][j] 表示 nums1第i个元素结尾 和 nums2第j个元素结尾 的最长公共子数组的长度
+3、初始化：
+  1）二维dp数组扩容：增加空数组这一最小规模的情况，方便直观初始化
+  2）dp[i][0] = dp[0][j] = 0 表示 空数组 和 任意数组 的最长公共子数组的长度为0。
+4、状态转移方程：
+  1）如果 nums1[i] == nums2[j]，即两个元素相同时，结果为 nums1第i-1个元素结尾 和 nums2第j-1个元素结尾 的最长公共子数组的长度 加1，即 dp[i][j] = dp[i - 1][j - 1] + 1;
+  2）如果 nums1[i] != nums2[j]，即两个元素不相同时，以这两个元素结尾的子数组也必然不相同，所以公共子数组的长度为0
+5、遍历dp数组填表：
+  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最长公共子数组的长度
+  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历数组nums1，内层遍历数组nums2。
+    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
+    从两个字符串角度看，两个指针分别指向两个数组，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
+6、返回结果：遍历过程比较并记录最长公共子数组的长度，最后返回结果
+
+nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7], findLength = 3
+    [] 3  2  1  4  7
+[]  0  0  0  0  0  0
+1   0  0  0  1  0  0
+2   0  0  1  0  0  0
+3   0  1  0  0  0  0
+2   0  0  2  0  0  0
+1   0  0  0  3  0  0
+
+nums1: 1  2  3  2  1
+                   ↑
+                   i
+nums2: 3  2  1  4  7
+             ↑
+             j
+ */
 class Solution {
     public int findLength(int[] nums1, int[] nums2) {
-        int n = nums1.length, m = nums2.length;
-        int res = 0;
+        int n = nums1.length, m = nums2.length, res = 0;
         int[][] dp = new int[n + 1][m + 1];
         for (int i = 1; i <= n; i++) {
             for (int j = 1; j <= m; j++) {
