经典dp 编辑距离

给定两个字符串S和T，对于T我们可以进行三种操作

（1）在任意位置增加字符

（2）删除字符

（3）替换字符

问最少多少次能把T变成S？

设f(i,j)是S的前i位和T的前j位对齐的最小花费

接下来分析每一位

（1）如果S[i]==T[j]，就不用任何修改，那么最小花费是f(i-1,j-1)

（2）如果S[i]!=T[j]，那么最小花费是f(i-1,j-1)+1

（3）如果S的前i位已经和T的前(j-1)位对齐了，那么最小花费是f(i,j-1)+1

（4）如果S的前(i-1)位已经和T的前j位对齐了，那么最小花费是f(i-1,j)+1

综上，递推式是f(i,j)=min(f(i,j)+cost,f(i-1,j)+1,f(i,j-1)+1)

最后分析一下初值：

f(i,0)=i

f(0,j)=j

这就相当与把S或T的前i或j位全部删除的样子（好残忍……）

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int f[][];

int main()

{

    char a[],b[];

    int lena,lenb,i,j,cost,mincost;

    while(~scanf("%s%s",a,b))

    {

        lena=strlen(a);

        lenb=strlen(b);

        for(i=; i<lena; i++)

            f[i][]=i;

        for(i=; i<lenb; i++)

            f[][i]=i;

        for(i=; i<=lena; i++)

            for(j=; j<=lenb; j++)

            {

                if(a[i-]==b[j-]) cost=;

                else cost=;

                mincost=min(f[i][j-]+,f[i-][j]+);

                f[i][j]=min(mincost,f[i-][j-]+cost);

            }

        printf("%d\n",f[lena][lenb]);

        memset(f,,sizeof(f));

    }

    return ;

}