题解 | #编辑距离(一)#

int editDistance(string str1, string str2) {
    //分别存储str1和str2的长度，为状态矩阵的大小做铺垫
    int n1 = str1.size();
    int n2 = str2.size();
    //状态矩阵，dp[i][j]表示str1[i]变换到str2[j]的最小操作数
    //这个说着容易，但是真正理解这里面的操作还是很难的
    //主要就是dp[i][j]是怎么过来的，怎么由之前的操作经过一些操作变换过来
    //注意矩阵的大小，也是很重要的
    vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0));
    //这个初值都是有点与众不同，下面的循环是对str1进行删除操作
    for(int i=0;i<=n1;i++){
        dp[i][0]=i;
    }
    //下面的循环是对str1进行插入操作
    for(int i=0;i<=n2;i++){
        dp[0][i]=i;
    } 
    //循环对dp[i][j]进行赋值，考虑到各种情况
    //此时就是从下标1开始了，小于等于n
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=n2;j++){
            //此时的下标是比实际大1的，需要减去1才是正确的
            //判断当前字符相等的情况，直接无视这两个字符，不进行操作
            //也就是考虑前面dp[i-1][j-1]的值，操作不需要增加
            if(str1[i-1]==str2[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }
            //这个就很重要了，我就卡到了这里，完全想不出来
            //对于dp[i][j]的值，与左上方三个值相关，每个正好对应一种操作,也就是从三个方向过来
            //dp[i][j-1]+1左边的+1表示str1[i]到str2[j]需要从str1[i]到str2[j-1]进行添加字符操作（添加str[j]字符）。
            //dp[j-1][i]+1右边的+1表示str1[i]到str2[j]需要从str1[j-]到str2[i]进行删除字符操作（删除str[j]字符）。
            //dp[i-1][j-1]+1左上方的+1表示str1[i]到str2[j]需要从str1[i-1]到str2[j-1]进行替换操作（str2[j]字符替换str1[i]字符）。
            else{
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
    }
    //返回最后的值
    return dp[n1][n2];
}