题目一：两个字符串的删除操作

力扣题目链接

题目描述：

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

思路分析：代码随想录

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
3. dp数组如何初始化：dp[i][0] = i
4. 确定遍历顺序：遍历顺序一定是从上到下，从左到右
5. 举例推导dp数组

解法： 

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; 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 len1 + len2 - dp[len1][len2] * 2;}
}

题目二：编辑距离

力扣题目链接

题目描述：

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

思路分析：代码随想录

1. 确定dp数组（dp table）以及下标的含义：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
2. 确定递推公式：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1
3. dp数组如何初始化：dp[0][j] = j
4. 确定遍历顺序：遍历顺序一定是从左到右，从上到下
5. 举例推导dp数组

解法： 

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 1; i <= m; i++) {dp[i][0] =  i;}for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (word1.charAt(i - 1) == word2.charAt(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[m][n];}
}