问题描述：
给定两个单词：word1以及word2，计算将word1转换成word2所需的最少操作数。
合法操作：
- 插入一个字符；
- 删除一个字符；
- 替换一个字符。
解题思路：
动态规划：
dp[i][j]: word1[0,i-1]->word2[0][j-1]所需的最少操作
当word1[i] = word2[j]:
dp[i][j] = dp[i-1][j-1];
当word1[i] != word2[j]:
三种可能：
替换：
dp[i][j] = dp[i-1][j-1] + 1;
删除：
dp[i][j] = dp[i][j-1] + 1;
dp[i][j] = dp[i-1][j] + 1;
因此：dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size();
int len2 = word2.size();
vector<vector<int>> dp;
dp.resize(len1+1);
for (int i=0;i<=len1;++i){
dp[i].resize(len2+1,0);
}
for (int i=1;i<=word2.size();++i){
dp[0][i] = i;
}
for (int i=1;i<=word1.size();++i){
dp[i][0] = i;
}
for (int start=0;start<word1.size();++start){
for (int end=0;end<word2.size();++end){
if (word1[start] == word2[end]){
dp[start+1][end+1] = dp[start][end];
continue;
}else{
dp[start+1][end+1] = min(dp[start][end],min(dp[start+1][end],dp[start][end+1]))+1;
}
}
}
return dp[len1][len2];
}
};
