Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
分析：
处理这道题也是用动态规划。
动态数组dp[word1.length+1][word2.length+1]
dp[i][j]表示从word1前i个字符转换到word2前j个字符最少的步骤数。
假设word1现在遍历到字符x，word2遍历到字符y（word1当前遍历到的长度为i，word2为j）。
以下两种可能性：
1. x==y，那么不用做任何编辑操作，所以dp[i][j] = dp[i-1][j-1]
2. x != y
(1) 在word1插入y， 那么dp[i][j] = dp[i][j-1] + 1
(2) 在word1删除x， 那么dp[i][j] = dp[i-1][j] + 1
(3) 把word1中的x用y来替换，那么dp[i][j] = dp[i-1][j-1] + 1
最少的步骤就是取这三个中的最小值。
最后返回 dp[word1.length+1][word2.length+1] 即可。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m+);
for(size_t i = ; i<m+; i++)
for(size_t j = ; j<n+; j++)
dp[i].push_back(-);
for(size_t i=; i<m+;i++)
dp[i][] =i;
for(size_t j=; j<n+; j++)
dp[][j] =j;
for(int i=; i<m+; i++)
for(int j =; j<n+; j++)
{
if(word1[i-] == word2[j-]){
dp[i][j] = dp[i-][j-];
}
else{
int insert = dp[i-][j]+;
int replace = dp[i-][j-]+;
int del = dp[i][j-]+;
dp[i][j] = min(del,min(insert, replace));
}
}
return dp[m][n];
}
};