給定兩個(gè)單詞 word1 和 word2，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：

• 插入一個(gè)字符
• 刪除一個(gè)字符
• 替換一個(gè)字符

舉例說(shuō)明：

輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

解釋：動(dòng)態(tài)規(guī)劃法dp[i][j]表示 word1的前i個(gè)字符與word2的前j個(gè)字符之間的編輯距離，則當(dāng)i||j==0時(shí)， dp[i][j] = 0+max(i,j).這一點(diǎn)很好理解。
一般情況：
如果word1[i-1][j-1] = = word 2[i-1][j-1] 時(shí)，則有：

• dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1]+1,dp[i-1][j]+1));

如果word1[i-1][j-1] ！= word 2[i-1][j-1]時(shí)，則有：

• dp[i][j] = dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0; i<dp.size();i++){
            for(int j=0;j<dp[0].size();j++){
                if(i==0||j==0) dp[i][j] = i+j;
                else if(word1[i-1]==word2[j-1]){
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1]+1,dp[i-1][j]+1));
                }
                else  dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1; 
            }
        }
        return dp[word1.size()][word2.size()];
    }
};