leetcode 72.edit distance

https://leetcode.com/problems/edit-distance/discuss/25846/20ms-Detailed-Explained-C++-Solutions-(O(n)-Space)

注意：初始化的时候，不再是以前那样[0,i]、[i,0]为0，而是相应的值。这是可以理解的，因为，[0,i]其实就相当于0个字符串变成i个字符需要花费的操作，这肯定是i个，即增加i个字符。

dp[i][j]表示前i个字符变成j个字符需要的最少操作个数

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