#Java #动态规划

Feeling and experiences：

编辑距离：力扣题目链接

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

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

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

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

该题的 dp数组定义 ， dp数组初始化 ，递推公式都比较难

主要涉及到了 三个操作：

insert，delete，replace

我对 dp数组的定义是：

 达到 word1 第 i 个字母 与到达 word2第 j 个 字母，最小操作数为dp[i][j]

如果用了该定义，就要对dp数组进行初始化！

class Solution {public int minDistance(String word1, String word2) {//insert delete replace 操作//编辑距离问题//创建dp数组 ，定义： 达到 word1 第 i 个字母 与到达 word2第 j 个 字母，最小操作数为dp[i][j]int [][]dp = new int[word1.length()+1][word2.length()+1];//有增删改 三个操作//初始化：for(int i =0;i<=word1.length();i++){dp[i][0] = i;}for(int j =0;j<=word2.length();j++){dp[0][j] = j;}//循环遍历，递推for(int i =1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){//插入删除可以合并：//word1 删除一个  或者  word2 删除一个（可以衍生为 word1加一个）if(word1.charAt(i-1) == word2.charAt(j-1)){//相等则保持上一个状态dp[i][j] = dp[i-1][j-1];}else{//进行 替换操作 ， 只需要替换一个 则 加 1//取最小结果dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; //Math.min 只能两两比较}}}return dp[word1.length()][word2.length()];}
}

这里对 增加 和 删除操作 做了一个巧妙的 合并：

因为 对于word1 增加 一个 字母的操作 ，也就是 word2 删除一个 字母的 操作！

总结思路：

• 定义状态： 创建一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑操作数。

• 初始化： 将 dp[i][0] 初始化为 i，表示将空字符串转换为 word2 的最小编辑操作数为 i；同理，将 dp[0][j] 初始化为 j，表示将 word1 转换为空字符串的最小编辑操作数为 j。

• 递推关系： 使用嵌套的循环遍历 word1 和 word2 的每个字符，通过比较字符是否相等来决定插入、删除或替换操作。如果字符相等，保持上一个状态；如果不相等，选择插入、删除或替换的最小编辑操作数。

两个字符串的删除操作：力扣题目链接

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

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

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

该题 需要对两个字符串进行 删除了

思路基本一致：

class Solution {public int minDistance(String word1, String word2) {//要对两个 字符串进行删除操作//定义dp数组 int[][] dp = new int[word1.length() + 1][word2.length() + 1];//初始化for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;//循环，递推for (int i = 1; i < word1.length() + 1; i++) {for (int j = 1; j < word2.length() + 1; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}}return dp[word1.length()][word2.length()];}
}

• 定义状态： 创建一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑操作数。

• 初始化： 将 dp[i][0] 初始化为 i，表示将空字符串转换为 word2 的最小编辑操作数为 i；同理，将 dp[0][j] 初始化为 j，表示将 word1 转换为空字符串的最小编辑操作数为 j。

• 递推关系： 使用嵌套的循环遍历 word1 和 word2 的每个字符，通过比较字符是否相等来决定删除、替换或插入操作。如果字符相等，保持上一个状态；如果不相等，选择删除、替换或插入的最小编辑操作数，分别加上对应的成本。

沙上并禽池上暝，

云破月来花弄影。

Fighting！