华为机试--字符串距离--c语言

1、距离用dp来计算，为dp[len1]dp[len2]
2、初始化str1距离，坐标为0 开始，dp[i][0]，表示字符串str1[i-1]到全删完的距离
3、初始化str2距离，坐标为0 开始，dp[0][i]，表示字符串str2[i-1]到全删完的距离
4、循环判断，当两个字符相等，则到这一步的距离为上一步的距离，即dp[i][j] = dp[i-1][j-1]
5、循环判断，当两个字符不相等，则到这一步的距离为上一步的距离dp[i-1][j-1]加一，或者dp[i-1][j]+1，或者dp[i][j-1]+1，取最小值
6、对dp[i-1][j]，dp[i][j-1]这两个不太理解，后面慢慢分析

#include<stdio.h>
#include<string.h>
int min(int a,int b){
    return a>b?b:a;
}
int main(void){
    char str1[1000],str2[1000];
    int dp[1000][1000];
    while (scanf("%s %s",str1,str2)!=EOF) {
        memset(dp, 0, sizeof(dp));
        int len1 = strlen(str1),len2=strlen(str2),m=0;
        //初始数据，将str1删除为空时，每位需要执行的步骤
        for (int i = 0; i<=len1; i++) {
            dp[i][0] = i;
        }
        //初始数据，将str2删除为空时，每位需要执行的步骤
        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(str1[i-1] == str2[j-1]){
                    m = dp[i-1][j-1];
                    dp[i][j] = m;
                }
                else{
                    m = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
                    dp[i][j] = m;
                }

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