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
思路：动态规划。将所要求的min step作为状态，dp[i][j]表示word2的前j各字符通过word1的前i各字符转换最少需要多少步。可以看到有两个以上的string，通常状态要定义为二维数组，表示两个字符串前几个字符之间的关系。
class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.length()==) return word2.length();
if(word2.length()==) return word1.length();
vector<vector<int>> dp(word1.length(), vector<int>(word2.length(),));
if(word1[]==word2[]) dp[][] = ;
else dp[][] = ;
for(int i = ; i < word1.length(); i++){
for(int j = ; j < word2.length(); j++){
if(i> && j>){
if(word1[i]==word2[j]){
dp[i][j] =min(min(dp[i-][j], dp[i][j-])+,dp[i-][j-]);
}
else{
dp[i][j]=min(min(dp[i-][j], dp[i][j-]),dp[i-][j-])+;
}
}
else if(i>){
if(word1[i]==word2[j]){
dp[i][j] =i;
}
else{
dp[i][j]=dp[i-][j]+;
}
}
else if(j>){
if(word1[i]==word2[j]){
dp[i][j] =j;
}
else{
dp[i][j]=dp[i][j-]+;
}
}
}
}
return dp[word1.length()-][word2.length()-];
}
};