Edit Distance (C++ code)

LeetCode Edit Distance, Apr 4 '12
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
 思路：经典DP题，设定数组A[i][j]表示配对word1前i位和word2前j位所需的次数。

int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int> > A(m+1,vector<int>(n+1));
        int i,j;

        for( i = 0; i <= m; i++) A[i][0] = i; 

        for(i = 1; i <= n; i++) A[0][i] = i;

       for( i = 1; i <= m; i++){
           for( j = 1; j <= n; j++ ){               
          //replace
          if(word1[i-1] == word2[j-1]) A[i][j]  = A[i-1][j-1];
          else A[i][j] = A[i-1][j-1] + 1;
         //insert or delete
         A[i][j] = min( A[i][j], min(A[i-1][j], A[i][j-1]) + 1 );
          }
     }

          return A[m][n];
    }