题目链接：72. 编辑距离 - 力扣（LeetCode）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数
你可以插入、删除、替换字符
定义dp[i][j]是将word1[0:i-1]转换成word2[0:j-1]所使用的最少操作数
如果word1[i-1]等于word2[j-1]，那么说明dp[i][j]=dp[i-1][j-1]，不需要操作，否则的话：
要么替换，需要将word1[0:i-2]转换成word2[0:j-2]，即dp[i][j]=dp[i-1][j-1] 1
要么插入，需要将word1[0:i-1]转换成word2[0:j-2]，即dp[i][j]=dp[i][j-1] 1
要么删除，需要将word1[0:i-2]转换成word2[0:j-1]，即dp[i][j]=dp[i-1][j] 1
取决于它们三个哪个最小，当然word中有一个为空的情况所需要的操作次数都是另一个的长度
代码语言：javascript复制class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int> > dp(m 1, vector<int>(n 1));
for (int i = 0; i <= m; i)dp[i][0] = i;
for (int i = 0; i <= n; i)dp[0][i] = i;
for (int i = 1; i <= m; i)
for (int j = 1; j <= n; j)
if (word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) 1;
return dp[m][n];
}
};
