edit distance

//dp[i][j]:表示A[0,i]和B[0,j]之间的最小编辑距离，
//设A[0,i]形式str1c,B[0,j]形式str2d
//1.c==d, dp[i][j] = dp[i-1][j-1];
//2.c != d
//2.1: c替换成d, dp[i][j] = dp[i-1][j-1] + 1;
//2.2: append d, dp[i][j] = dp[i][j-1] + 1;
//2.3: delete d, dp[i][j] = dp[i-1][j] + 1;
int minDistance(string word1, string word2) {
    int len1 = word1.size();
    int len2 = word2.size();
    
    vector<vector<int> >dp(len1+1,vector<int>(len2+1,0));
    
    //初始化
    for(int i=0; i<=len1; i++){
        dp[i][0] = i;
    }
    for(int i=0; i<=len2; i++){
        dp[0][i] = i;
    }
    
    for(int i=1; i<=len1; i++){
        for(int j=1; j<=len2; j++){
            if(word1[i-1] == word2[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[len1][len2];
}