今日知识点

经典面试题：最长公共子序列问题
1. 题目描述
  
  输入: str1 = "abcde", str2 = "ace"
  输出: 3
  解释: 最长公共子序列是 "ace"，它的长度是 3
2. 解题思路
  
  子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有***都需要动态规划来解决
  
  第一步，一定要明确dp数组的含义。dp[i][j]的含义是：对于s1[1..i]和s2[1..j]，它们的 LCS 长度是dp[i][j]
  
  第二步，定义 base case。dp[0][..]和dp[..][0]都应该初始化为 0，这就是 base case，因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0
  
  第三步，找状态转移方程
3. 延伸拓展
  
  最长公共子序列问题，它的解法就是典型的二维动态规划，大部分困难的字符串问题都可以使用相似的解法来解决，例如编辑距离问题
解决两个字符串的动态规划问题：

一般来说，解决两个字符串的动态规划问题，解题思路一般都是用两个指针i,j分别指向两个字符串的末尾，然后一步步向前走，缩小问题的规模

LeetCode算法

72.【编辑距离】

解题思路：

求最小操作数，首先往动态规划上想，则这就是两个字符串的动态规划问题，则用两个指针i,j分别指向两个字符串的末尾，然后一步步向前走，缩小问题的规模

base case是i走完s1或j走完s2，可以直接返回另一个字符串剩下的长度。对于每对儿字符s1[i]和s2[j]，可以有四种操作，如果相同，则i,j同时前移动，此时操作数不变；否则，在插入、删除、替换中选择一个进行，操作数+1。最终，选择操作数最小的。至此，我们可以直接列出状态转移方程，状态为i,j，f(i, j)表示操作数，并且根据状态转移方程，我们就可以写出暴力解：

 public int dp(String word1, String word2, int i, int j) {
 // base case
 if (i == -1) return j + 1; // 当i=-1，说明s1已经完毕，因此只需要将s2剩下的字符都插入到s1即可，因此剩余的操作数为j+1
 if (j == -1) return i + 1; // 同理

 if (word1.charAt(i) == word2.charAt(j)) {
     // i,j位置字符相等，操作数不变
     return dp(word1, word2, i - 1, j - 1);
 } else {
     return Math.min(
         Math.min(
             dp(word1, word2, i - 1, j) + 1, // 将s1的i位置字符删除
             dp(word1, word2, i, j - 1) + 1 // 将s2的j位置字符，插入到s1
         ), 
         dp(word1, word2, i - 1, j - 1) + 1 // 将s2的j位置字符，与s1的i位置字符替换 
     );
 }
}

看暴力解法，可以知道，暴力解法就是一个多叉树的遍历，并且可以看出，暴力解有重叠子问题，因此，我们可以用DP Table来优化暴力解法，即使用动态规划解决。

public int dp(String word1, String word2, int i, int j) {
 int[][] dpTable = new int[i + 1][j + 1]; // dpTable的dpTable[0][..]和dpTable[..][0]存储base case
 // base case
 for (int m = 1; m <= i; m++) {
     dpTable[m][0] = m;
 }
 for (int n = 1; n <= j; n++) {
     dpTable[0][n] = n;
 }

 // 自低向上遍历
 for (int p = 1; p <= i; p++) {
     for (int q = 1; q <= j; q++) {
         if (word1.charAt(p - 1) == word2.charAt(q - 1)) {
             dpTable[p][q] = dpTable[p - 1][q - 1];
         } else {
             int temp = Math.min(dpTable[p - 1][q] + 1, dpTable[p][q - 1] + 1);
             dpTable[p][q] = Math.min(temp, dpTable[p - 1][q - 1] + 1);
         }
     }
 }

 return dpTable[i][j];

}

2021/05/18 今日算法

今日知识点

LeetCode算法