DP…这里只是求编辑距离，有时候可能还要回溯找到发生了什么…

DP...这里只是求编辑距离，有时候可能还要回溯找到发生了什么...

令f[i][j]表示a串前i个，b串前j个的编辑距离
状态转移：
若a串第i个与b串第j个相等，那么f[i][j]=f[i-1][j-1]
否则，f[i][j]可由3个状态转移而来：
①f[i-1][j-1]+ f(i, j) 当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
②f[i-1][j]+1 删去a[i]，等价于在b[j]后插入a[i]（删除就相当于插入了）
③f[i][j-1]+1 删去b[j]，等价于在a[i]后插入b[j]
初始化:f[0][i]=i  f[i][0]=i

int dp[1010][1010];
int main()
{
    char a[1010],b[1010];
    int i,j;
    gets(a);gets(b);
    for(i=0;i<=strlen(a);i++)
    dp[i][0]=i;
    for(i=0;i<=strlen(b);i++)
    dp[0][i]=i;
    for(i=1;i<=strlen(a);i++)
    for(j=1;j<=strlen(b);j++)
    if(a[i-1]==b[j-1])dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]);     //这里注意a[i-1],a是从0开始的 
    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[strlen(a)][strlen(b)]);
    return 0;
}