leetcode第一刷_Edit Distance

最小編輯距離，很經典的問題，今年微軟實習生的筆試有一個這個的擴展版，牽扯到模板之類的，當時一行代碼也沒寫出來。。

dp可以很優雅的解決這個問題，狀態轉移方程也很明確。用pos[i][j]表示word1的前i個字符與word2的前j個字符之間的編輯距離。如果word[i-1]與word[j-1]相等，那pos[i][j]與pos[i-1][j-1]相等，否則的話，根據編輯的幾種操作，可以從三種情況中選取代價最小的一種，從word1中刪除一個字符？從word2中刪除一個字符？修改其中一個？邊界也很簡單，一個字符串長度為0時，編輯距離一定是根據另一個的長度不斷增加的。

寫成代碼一目了然：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        int pos[len1+1][len2+1];
        for(int i=0;i<=len1;i++)
            pos[i][0] = i;
        for(int i=0;i<=len2;i++)
            pos[0][i] = i;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(word1[i-1] == word2[j-1])
                    pos[i][j] = pos[i-1][j-1];
                else{
                    pos[i][j] = min(pos[i-1][j], min(pos[i-1][j-1], pos[i][j-1]))+1;
                }
            }
        }
        return pos[len1][len2];
    }
};