目录
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
? ? ? ? ?按照求最长子序列的思路来做，得到最长的公共length值，用两个字符串的长度减去两个公共length 就是最长公共子序列的长度
? ? ? ? 公共最长子序列的求法
? ? ? ? dp[i][j] 为0~i-1 0~j-1的最长序列
? ? ? ? 递推公式
? ? ? ? 若相同，dp[i][j] = dp[i-1][j-1]+1
? ? ? ? 若不相同,二选一 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
? ? ? ?
????????
? ? ? ? 用动态规划，使用了删除的思路
? ? ? ? (选中两个单词的字符，判断删除哪一个)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ??
? ? ? ? dp[i][j]记录末尾为i-1和j-1的最少删除字符的个数
????????
? ? ? ? 确定递推公式
? ? ? ? 要从递推公式来进行考虑
? ? ? ?若word1[i] = word2[j] 则不管是否选中word1 和word2 和不选中word1和word2都一样，不需要新增删除的次数，总删除的次数和之前相等
????????????????dp[i][j] = dp[i-1][j-1];?
????????若word1[i] !=word2[j] 则从之前的删除次数最小值 来考虑
? ? ? ? ? ? ? ? 若选中word1来删除
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i-1][j]+1
? ? ? ??
????????????????若选中word2来删除
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i][j-1]+1
? ? ? ? ? ? ? ? 若都不选中，两者都删
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i-1][j-1]+2
? ? ? ? ? ? ? ? 之前的最长子序列是dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1，dp[i-1][j-1]+2);
? ? ? ? ? ? ? ?
???????? dp数组初始化
? ? ? ? ? ? ? ? ? 因为dp[i][j] 代表0~i-1，0~j-1的最大删除次数，
????????????????则dp[i][0] = i
???????????????????dp[0][j] = j （含义：若把j变成0 需要删除j次）
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后，从上往下
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 打印最后一个元素
? ? ? ????????????????? 疑问？为什么选最小的？不相同时不应该两个都要删吗？
? ? ? ? ? ? ? ? ? ? ? ? 不是两个都要删，而是判断不相同了，一次只删一个，选择哪一个
? ? ? ? ? ? ? ? ? ? ? ? 两个不相等，模拟一下这个双重循环，其实i固定不变，只是在动j
? ? ? ? ? ? ? ? ? ? ? ?遇到两个单词中不相等的字符，来通过dp来判断应该删除哪一个，二维数组是动态变化的
? ? ? ? ? ? ? ? ? ? ?最小的删除个数，从之前中选择最小的
class Solution {
public int minDistance(String word1, String word2) {
/*
//我的做法
//相同的最小步数
//其实就是看公共子序列的最大长度？，然后看删去需要多少个字符？
//确定dp的定义和下标的含义
// dp[i][j] 0~i-1的word1 和 0~j-1的相同公共子序列的长度
//确定递推公式
// 若word[i-1]==word[j-1] 则dp[i][j]=dp[i-1][j-1]+1
// 若不相等 则dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
//dp数组初始化
// 都为0
//确定遍历顺序
// 从上往下，从左至右
//打印dp数组
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i=1;i<=word1.length();i++){
for(int j=1;j<=word2.length();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][j-1],dp[i-1][j]);
}
}
}
int maxLength = dp[word1.length()][word2.length()];
return word1.length()+word2.length()-2*maxLength;*/
//卡哥的做法
//确定dp的定义和下标的含义
// dp[i][j] 代表删除字符的最小的个数
//确定递推公式
// 如何删除
// word1[i-1]==word2[j-1] 若相等 考虑选中word1[i-1] 和word2[j-1] 和不选中word1[i-1]和word2[j-1]
// dp[i][j] = dp[i-1][j-1]，因为相等，所以 都考虑和都不考虑，最小删除的个数都是一样的
// word1[i]!=word2[j] 若不相等 ，考虑最小删除的个数，有三种情况
// 若不选中word1 则为 dp[i-1][j]+1
// 若不选中word2 则为 dp[i][j-1]+1
// 若不都选中 dp[i-1][j-1] +2 去三者中的最小值
//dp数组初始化
// dp[i][0] = i word1 有值，word2为空串
// dp[0][j] = j word2 有值，word1为空串
//确定遍历顺序
// 从上往下，从左至右
//打印dp数组
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++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
// 疑问？为什么选最小的？不相同时不应该两个都要删吗？
// 不是两个都要删，而是判断不相同了，一次只删一个，选择哪一个
// 两个不相等，模拟一下这个双重循环，其实i固定不变，只是在动j
// 看两个单词中不相等的字符，来看通过dp来判断应该删除哪一个，二维数组是动态变化的
//最小的删除个数，从之前中选择最小的
dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
}
}
}
return dp[word1.length()][word2.length()];
}
}给你两个单词?word1 和?word2，请你计算出将?word1?转换成?word2 所使用的最少操作数?。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例?1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例?2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
? ? ? ?按上一题的思路来做
????????
? ? ? ? 用动态规划，使用了删除的思路
? ? ? ? (选中两个单词的字符，判断删除哪一个)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ??
? ? ? ? dp[i][j]记录末尾为i-1和j-1的最少删除字符的个数
????????
? ? ? ? 确定递推公式
? ? ? ? 要从递推公式来进行考虑
? ? ? ?若word1[i] = word2[j] 则不管是否选中word1 和word2 和不选中word1和word2都一样，不需要新增删除的次数，总删除的次数和之前相等
????????????????dp[i][j] = dp[i-1][j-1];?
????????若word1[i] !=word2[j] 则从之前的删除次数最小值 来考虑
? ? ? ? ? ? ? ? 若选中word1来删除
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i-1][j]+1
? ? ? ??
????????????????若选中word2来删除
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i][j-1]+1
? ? ? ? ? ? ? ? 若都不选中，两者都删
? ? ? ? ? ? ? ? 之前的总删除次数为dp[i-1][j-1]+2
? ? ? ? ? ? ? ? 之前的最长子序列是dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1，dp[i-1][j-1]+2);
? ? ? ? ? ? ? ?
???????? dp数组初始化
? ? ? ? ? ? ? ? ? 因为dp[i][j] 代表0~i-1，0~j-1的最大删除次数，
????????????????则dp[i][0] = i
???????????????????dp[0][j] = j （含义：若把j变成0 需要删除j次）
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后，从上往下
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 打印最后一个元素
? ? ? ????????????????? 疑问？为什么选最小的？不相同时不应该两个都要删吗？
? ? ? ? ? ? ? ? ? ? ? ? 不是两个都要删，而是判断不相同了，一次只删一个，选择哪一个
? ? ? ? ? ? ? ? ? ? ? ? 两个不相等，模拟一下这个双重循环，其实i固定不变，只是在动j
? ? ? ? ? ? ? ? ? ? ? ?遇到两个单词中不相等的字符，来通过dp来判断应该删除哪一个，二维数组是动态变化的
? ? ? ? ? ? ? ? ? ? ?最小的删除个数，从之前中选择最小的