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

#include<stdio.h>
#include<string.h>
int main(void)
{
    char str1[1001]={0};
    char str2[1001]={0};
    scanf("%s%s",&str1,&str2);
    int len1=strlen(str1);
    int len2=strlen(str2);
    int dp[1002][1002]={0};
    //初始化dp数组
    for(int i=0;i<=len1;i++)
    {
        dp[0][i]=i;
    }
    for(int i=0;i<=len2;i++)
    {
        dp[i][0]=i;
    }
    //开始计算dp数组
    int min=0;
    for(int i=1;i<=len2;i++)
    {
        for(int j=1;j<=len1;j++)
        {
            //此处是str1[j-1]和str2[i-1],易错，因为dp数组的行列宽度都比str大1
            if(str1[j-1]==str2[i-1]){dp[i][j]=dp[i-1][j-1];}
            else
            {
                min=dp[i-1][j-1]+1;
                if(min>(dp[i][j-1]+1)){min=(dp[i][j-1]+1);}
                if(min>(dp[i-1][j]+1)){min=(dp[i-1][j]+1);}
                dp[i][j]=min;
            }
        }
    }
    printf("%d",dp[len2][len1]);
    return 0;
}