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

linwt · linwt · commit ff0f28227435 · 2022-03-24T00:03:14.000+08:00
diff --git a/leetcode_Java/Solution0072.java b/leetcode_Java/Solution0072.java
@@ -10,7 +10,7 @@
   2）扩增dp数组，int[][] dp = new int[n+1][m+1]，dp[0][0]表示两个都是空字符，首行首列表示至少其中一个字符串为空字符的情况
   3）注意第 i 个字符在字符串中为 word1.charAt(i - 1)，索引从0开始
 4、初始化：
-  1）针对首行首列要单独考虑，引入''。列表示word1，行表示word2
+  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
   2）第一行是word1为空，word1转换成word2使用的最少操作数，就是插入操作
   3）第一列是word2为空，word1转换成word2使用的最少操作数，就是删除操作
   4）首行首列操作数进行累加初始化
@@ -27,13 +27,13 @@
   3）dp[i-1][j] 表示插入操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符
 7、遍历dp数组填表：
   1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
-  2）外层遍历word1，内层遍历word2。
-    从二维数组角度看，顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
-    从两个字符串角度看，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+  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、返回结果：最后一个状态就是结果
 
+word1 = "horse", word2 = "ros"
    ''  r   o   s
 '' 0   1   2   3
 h  1   1   2   3
diff --git a/leetcode_Java/Solution0115.java b/leetcode_Java/Solution0115.java
@@ -2,7 +2,49 @@
 
 
 /*
+动态规划：
+1、题目简化：求s的子序列中t出现的个数
+1、定义dp数组：dp[i][j] 表示 s前i个字符 中出现 t前j个字符 的个数
+2、初始化：
+  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
+  2）dp[i][0] = 1 表示 s前i个字符 中出现 t前0个字符 的个数为1，即空字符串是任何字符串的子集
+     dp[0][j] = 0 表示 s前0个字符 中出现 t前j个字符 的个数为0，即空字符串不会出现任何字符串
+     dp[0][0] = 1 表示 s前i个字符 中出现 t前0个字符 的个数为1，即空字符串是空字符串的子集
+3、状态转移方程：
+  1）s中不同索引位置的字符组合，代表不同的子序列
+  2）如果s[i] == s[j]，那么s有两种方式可以匹配t
+    第一种是用s[i]匹配掉t[j]，那么出现个数为 s前i-1个字符中出现t前j-1个字符的个数，即 dp[i - 1][j - 1]
+    第二种是不用s[i]匹配t[j]，那么出现个数为 s前i-1个字符中出现t前j个字符的个数，即 dp[i - 1][j]
+    所以 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
+  3）如果s[i] != s[j]，那么s只能不用s[i]匹配t[j]，那么出现个数为 s前i-1个字符中出现t前j个字符的个数，即 dp[i - 1][j]
+    所以 dp[i][j] = dp[i - 1][j];
+4、遍历dp数组填表：
+  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的出现个数
+  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串s，内层遍历字符串t。
+    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
+    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j] 都是已知状态了
+5、返回结果：最后一个状态就是结果
 
+s = "babgbag", t = "bag"
+二维数组：
+  ''  b  a  g
+'' 1  0  0  0
+b  1  1  0  0
+a  1  1  1  0
+b  1  2  1  0
+g  1  3  1  1
+b  1  3  4  1
+a  1  3  4  1
+g  1  3  4  5
+
+字符串：
+s:  b  a  b  g  b  a  g
+                      ↑
+                      i
+t:  b  a  g
+          ↑
+          j
  */
 class Solution {
     public int numDistinct(String s, String t) {
diff --git a/leetcode_Java/Solution0392.java b/leetcode_Java/Solution0392.java
@@ -2,7 +2,7 @@
 
 
 /*
-实际就是“1143.最长公共子序列”
+求字符串t是否为字符串s的子序列，实际就是“1143.最长公共子序列”，得到最长长度再判断是否等于t的长度
  */
 class Solution {
     public boolean isSubsequence(String s, String t) {
diff --git a/leetcode_Java/Solution0516.java b/leetcode_Java/Solution0516.java
@@ -1,6 +1,52 @@
 // 516. 最长回文子序列
 
 
+/*
+动态规划：
+1、题目简化：求字符串s的最长回文子序列的长度
+2、定义dp数组：dp[l][r] 表示字符串在区间s[l,r]的最长回文子序列的长度
+3、初始化：
+  1）二维dp数组不用扩容，直接根据dp数组的定义就可以直观地对应进行初始化
+  2）dp[i][i] = 1 表示每个字符的最长回文子序列的长度为1
+4、状态转移方程：
+  1）如果s[l] == s[r]，即区间首尾两个字符相同，由于l<r，所以有两种情况
+     ① 两个字符相邻，中间没有字符，则 r-l == 1，此时最长回文子序列的长度为2个字符，即 dp[l][r] = 2
+     ② 两个字符不相邻，中间有字符，那么结果为 中间的字符的最长回文子序列的长度加2个字符，即 dp[l][r] = dp[l + 1][r - 1] + 2
+  2）如果s[l] != s[r]，即区间首尾两个字符不相同，那么长度不能增加，只能使用之前状态的最长长度，有两种情况是状态已知且字符最多的
+     ① 去掉s[l]，即区间s[l+1,r]的最长回文子序列的长度，即dp[l + 1][r]
+     ② 去掉s[r]，即区间s[l,r-1]的最长回文子序列的长度，即dp[l][r - 1]
+     比较这两种情况是因为去掉的字符可能刚好是一个回文字符，两者取最大就得到当前结果，即 dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1])
+5、遍历dp数组填表：
+  1）两个for循环遍历二维dp数组右上角每个位置，根据状态转移方程计算该位置的最长回文子序列的长度
+  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历右区间，内层遍历左区间。
+    从二维数组角度看，遍历顺序是从左到右，从下到上，所以遍历到(l,r)位置时，其左方、下方、左下方状态都已经遍历计算过了。
+    从字符串角度看（更好理解），两个指针分别指向字符串的左右区间，右指针 从左到右遍历，左指针 从右到左遍历，所以遍历到(l,r)位置时，其中间其他位置都遍历计算过了。
+    由于新状态的转移需要依赖 不含首尾的中间区间 和 含首尾之一的中间区间 的旧状态，所以决定了这样的遍历顺序
+    所以求 dp[l][r] 时，dp[l + 1][r - 1]、 dp[l + 1][r]、dp[l][r - 1]都是已知状态了
+6、返回结果：遍历过程比较并记录每个区间中的最长回文子序列的长度，最终返回最大值
+
+s = "bdccbe", lps = "bccb"
+   b  d  c  c  b  e
+b  1  1  1  2  4  4
+d     1  1  2  2  2
+c        1  2  2  2
+c           1  1  1
+b              1  1
+e                 1
+
+
+b  d  c  c  b  e
+      ↑  ↑
+      l  r
+
+b  d  c  c  b  e
+↑           ↑
+l           r
+
+b  d  c  c  b  e
+↑              ↑
+l              r
+ */
 class Solution {
     public int longestPalindromeSubseq(String s) {
         int n = s.length(), res = 1;
diff --git a/leetcode_Java/Solution1143.java b/leetcode_Java/Solution1143.java
@@ -1,6 +1,44 @@
 // 1143. 最长公共子序列
 
 
+/*
+动态规划：
+1、题目简化：求字符串t1和字符串t2的最长公共子序列的长度
+2、定义dp数组：dp[i][j] 表示 t1的前i个字符 和 t2的前j个字符 的最长公共子序列的长度
+3、初始化：
+  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化。列表示t1，行表示t2
+  2）dp[i][0] = dp[0][j] = 0 表示空字符串与另一字符串的最长公共子序列的长度为0。创建二维数组时默认为0了
+4、状态转移方程：
+  1）如果t1[i] == t2[j]，即两个字符串最后一个字符相同，那么结果为 t1的前i-1个字符 和 t2的前j-1个字符 的最长公共子序列的长度加1，即 dp[i][j] = dp[i - 1][j - 1] + 1;
+  2）如果t1[i] != t2[j]，即两个字符串最后一个字符不相同，那么长度不能增加，只能使用之前状态的最长长度，有两种情况是状态已知且字符最多的
+      ① 去掉t1[i]，即 t1的前i-1个字符 和 t2的前j个字符 的最长公共子序列的长度，即 dp[i - 1][j]
+      ② 去掉t2[j]，即 t1的前i个字符 和 t2的前j-1个字符 的最长公共子序列的长度，即 dp[i][j - 1]
+      比较这两种情况是因为去掉的字符可能刚好是一个公共字符，两者取最大就得到当前结果，即 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
+5、遍历dp数组填表：
+  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最长公共子序列的长度
+  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串t1，内层遍历字符串t2。
+    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
+    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
+    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
+6、返回结果：最后一个状态就是结果
+
+t1 = "abcde", t2 = "ace"
+   '' a  c  e
+'' 0  0  0  0
+a  0  1  1  1
+b  0  1  1  1
+c  0  1  2  2
+d  0  1  2  2
+e  0  1  2  3
+
+        t1[i] != t2[j]       t1[i] == t2[j]
+text1:  a  b  c  d  e        a  b  c  d  e
+                 ↑                       ↑
+                 i                       i
+text2:  a  c  e              a  c  e
+           ↑                       ↑
+           j                       j
+ */
 class Solution {
     public int longestCommonSubsequence(String text1, String text2) {
         int n = text1.length(), m = text2.length();
