共计 1102 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
1. 插入一个字符 2. 删除一个字符 3. 替换一个字符
解答：这一题用动态规划，dpi 表示 word1 中 0 到 i 的字符所组成的字符串到 word2 中 0 到 j 的字符所组成的字符串的编辑距离。那么答案则为 dpword1.length 那么如何求 dpi 呢？也就是转移方程。由定义可以知道空字符串变成任意长度字符串的代价为该字符串的长度，也就是说 dp0 = j+1,dpi = i+1。这里的 i，j 最大分别为 word1 和 word2 的长度 -1。对于 dpi, 若 word1[i] != word2[j]，那么 dpi = 1 + min(dpi-1,dpi), 这里的解释为删除 word1[i] 或者删除 word2[j], 并且比较 word1[0-i-1] 变成 word2[0-j] 和 word1[0-i] 变成 word2[0-j-1] 的大小，选择小的那个。若 word1[i] == word2[j]，那么 dpi = min(dpi-1,1 + min(dpi-1,dpi)) 这里的解释是，增加了一个比较对象，word1[0-i-1] 变成 word2[0-j-1]。java ac 代码：
class Solution {
public int minDistance(String word1, String word2) {
if(word1.length() == 0||word2.length() == 0)return Math.max(word1.length(),word2.length());
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++)
{
int ans = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
if(word1.charAt(i-1) == word2.charAt(j-1))
ans = Math.min(ans,dp[i-1][j-1]);
dp[i][j] = ans;
}
return dp[word1.length()][word2.length()];
}
}