编辑距离问题

编辑距离问题，直接套公式就可以了，但是这里的话需要说明一下 dp[i-1][j] 是删除，将第i个删除，然后i-1 和j 进行比较 dp[i][j-1] 是插入 插入一个和j 位置一样的值， 再去比较i 和 j-1的大小 dp[i-1][j-1] 如果ij 位置相同，那么什么都不用做，就是等于 i-1 j-1 位置的值的，如果不相等那么就是做了一次转换，编辑距离一定是这三种操作里面的最小值，这是一个理解起来比较复杂，但是解法简单的习题，下面贴代码，我是按照动态规划的方式去解的，这个题的话按照递归的思想也可以。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char str1[1005],str2[1005];
int dp[1005][1005];
int main(){
    while(scanf("%s %s",str1,str2)!=EOF){
        memset(dp,0,sizeof(dp));
        int len1=strlen(str1);
        int len2=strlen(str2);
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
                }
            }
        }
        printf("%d\n",dp[len1][len2]);
    }
    return 0;
}