8.15 dp srambleStr & minimumPathSum & editDistance

- to do

edit distance

• naive
• if (word1[i] == word2[j]) { return rec(word1, word2, i-1, j-1); garenteed to be opted?

    int rec(string& word1, string& word2, int i, int j) {
        if (i<0) return j+1;
        if (j<0) return i+1;
        if (word1[i] == word2[j]) {
            return rec(word1, word2, i-1, j-1);
        } else {
            return min(min(rec(word1, word2, i, j-1),
                           rec(word1, word2, i-1, j)),
                       rec(word1, word2, i-1, j-1))+1;
        }
        return -1; //should not reach
    }
    
    int minDistance(string word1, string word2) {
        return rec(word1, word2, word1.size()-1, word2.size()-1);
    }

• what's wrong??

    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size(), i, j;
        int dp[m+2][n+2] = {0}; //dp[i][j] holds minDistance of word1[i-1~m-1] & word2[j-1~n-1] 
        for (i=m; i>=0; --i) {
            for (j=n; j>=0; --j) {
                if (!i) {
                    dp[i][j] = j + dp[1][j+1];
                } else if (!j) {
                    dp[i][j] = i + dp[i+1][1];
                } else if (word1[i-1]==word2[j-1]) {
                    dp[i][j] = dp[i+1][j+1];
                } else {
                    dp[i][j] = min(min(dp[i+1][j], 
                                       dp[i][j+1]), 
                                   dp[i+1][j+1])+1;
                }
                cout<<"dp["<<i<<"]["<<j<<"]: "<<dp[i][j]<<endl;
            }
            
        }
        return dp[0][0];
    }