题解 | 计算字符串的编辑距离

#include <iostream>
using namespace std;
int ptr[1010][1010];
int main() {
    string s1,s2,s ="";cin>>s1>>s2;
    int len1 = s1.size();
    int len2 = s2.size();
    int res = 0;
    for(int i = 0;i<=len1;i++){
        ptr[i][0] = i;
    }
    for(int i = 0;i<=len2;i++){
        ptr[0][i] = i;
    }

    for(int i = 1;i<=len1;i++){
        for(int j = 1;j<=len2;j++){
            int d;
            int tem = min(ptr[i-1][j]+1,ptr[i][j-1]+1);
            if(s1[i-1]==s2[j-1]){
                d= 0;
            }
            else{
                d = 1;
            }
            ptr[i][j] = min(tem,ptr[i-1][j-1]+d);
        }
    }
    cout<<ptr[len1][len2]<<'\n';
    return 0;
}
// 64 位输出请用 printf("%lld")

可以使用动态规划的方法去测量DP的值，步骤大致如下：

初始化一个DP矩阵(M,N)，M和N分别是两个输入字符串的长度。

矩阵可以从左上角到右下角进行填充，每个水平或垂直跳转分别对应于一个插入或一个删除。

通过定义每个操作的成本为1，如果两个字符串不匹配，则对角跳转的代价为1，否则为0，简单来说就是：

如果[i][j]位置的两个字符串相等，则从[i][j]位置左加1，上加1，左上加0，然后从这三个数中取出最小的值填充到[i][j]。

如果[i][j]位置的两个字符串不相等，则从[i][j]位置左、左上、上三个位置的值中取最小值，这个最小值加1（或者说这三个值都加1然后取最小值），然后填充到[i][j]。

按照上面规则LD矩阵(M,N)填充完毕后，最终矩阵右下角的数字就是两个字符串的LD值。

活动地址https://www.nowcoder.com/discuss/726480854079250432