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

#include <stdio.h>
#include <string.h>
#define MIN(a,b,c) ((a)>(b)?((b)>(c)?(c):(b)):((a)>(c)?(c):(a)))
int main() {
    char str1[1001], str2[1001];
    while (scanf("%s %s", str1, str2) != EOF) {
        int len1 = strlen(str1);
        int len2 = strlen(str2);

        int dp[1000+1][1000+1];
        //初始状态
        for(int i=0;i<len1+1;i++)
        {
            //str2为空，str1只有前i个字符时，需要添加i个字符，即修改i次
            dp[i][0] = i;
        }
        for(int i=0;i<len2+1;i++) //同理
        {
            //str1为空，str2只有前i个字符时，需要添加i个字符，即修改i次
            dp[0][i] = i;
        }

        for(int i=1;i<len1+1;i++)   //子问题：str1只有前i个字符时的情况
        {
            for(int j=1;j<len2+1;j++)   //用整个str2去匹配str1的第i个字符
            {
                if(str1[i-1] == str2[j-1])  //当前字符相等
                {
                    //则不需要增加编辑次数 对str1和str2来说 当前字符加不加都一样
                    dp[i][j] = dp[i-1][j-1];    //继承上一个字符的次数即可
                }else {
                    //需要找到str1的第i个字符对应的str2的第j个字符的最小编辑次数
                    //因此需要分别比较str1 和 str2上一个字符+一次编辑的最小值
                    dp[i][j] = MIN(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1);
                }
            }
        }

        printf("%d",dp[len1][len2]);
    }
    return 0;
}