Edit Distance -interesting

Use dp[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):
if c == d, then : dp[i][j] = dp[i-1][j-1]
Otherwise we can use three operations to convert word1 to word2:
(a) if we replaced c with d: dp[i][j] = dp[i-1][j-1] + 1;
(b) if we added d after c: dp[i][j] = dp[i][j-1] + 1;
(c) if we deleted c: dp[i][j] = dp[i-1][j] + 1;


class Solution {
public:
    int minDistance(string word1, string word2) {
        return minDistance_2(word1, word2);
    }
    int minDistance_1(string word1, string word2) {
        int M = word1.size(), N = word2.size();
        int dp[N+1][M+1];
        for (int j = 0; j <= M; j++)
            dp[0][j] = j;
        for (int i = 0; i <= N; i++)
            dp[i][0] = i;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (word2[i-1] == word1[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
        return dp[N][M];
    }
    int minDistance_2(string word1, string word2) {
        int M = word1.size(), N = word2.size();
        int dp[N+1];
        for (int j = 0; j <= N; ++j)
            dp[j] = j;
        for (int i = 1; i <= M; ++i)
        {
            int upperLeftBackup = dp[0];
            dp[0] = i;
            for (int j = 1; j <= N; ++j)
            {
                int upperLeft = upperLeftBackup;
                upperLeftBackup = dp[j];
                if (word1[i-1] == word2[j-1])
                    dp[j] = upperLeft;
                else
                    dp[j] = min(min(dp[j-1], dp[j]), upperLeft) + 1;
            }
        }
        return dp[N];
    }
};