#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！