2988:计算字符串距离

总时间限制: 1000ms
内存限制: 65536kB

描述

对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：
修改一个字符（如把“a”替换为“b”）
删除一个字符（如把“traveling”变为“travelng”）

比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串，写出一个算法来计算出他们的距离。

输入

第一行有一个整数n。表示测试数据的组数，
接下来共n行，每行两个字符串，用空格隔开。表示要计算距离的两个字符串
字符串长度不超过1000。

输出

针对每一组测试数据输出一个整数，值为两个字符串的距离。

样例输入

3
abcdefg  abcdef
ab ab
mnklj jlknm

样例输出

1
0
4

【我的思想】

看到此题的我，第一个反应是想说：啧啧啧，这种题还用得着动态规划来做，我直接用函数做不就得了？心动就得行动，不用说，我快速的把函数思想码了出来…结果显而易见，我错了…至于为甚？我发现了一个盲点（我想只有我才认为这是一个盲点吧 —.—）。例如，输入open openg ,我的思想是先用strlen算出它的长度，然后相减取绝对值。num=相减后的绝对值。最后以最小的长度来搜前面四个单词有无异样，若有异样（num++）。但是，这样做有一个问题，例如，如果你输入body boody,正确的情况下是输出1，但是运用我的思想的话，就会输出3(过程如下：5-4==1，然后比较body与bood，如此一来，自然不行，因为会num+=2)，那么如何解决呢？请看代码。

【代码】

我的思想（错误代码）
状态： Wrong Answer

#include<cstdio>
#include<cstring>
#include<cmath>
int n,lena,lenb,m,max;
char a[2000],b[2000];//记住开大数组喔
int num;
void same()
{num=0;for(int i=0;i<lena;i++)//判断如果字符不相等if(a[i]!=b[i]) num++;
}
void different()
{m=lena>lenb? lenb:lena;max=fabs(lena-lenb);    num=max;for(int i=0;i<m;i++)if(a[i]!=b[i]) num++;
}
int main()
{scanf("%d",&n);while(n--){scanf("%s%s",a,b);lena=strlen(a);lenb=strlen(b);if(lena==lenb) same();else different();printf("%d\n",num);}
}

经过修改（AC）：
状态： Accepted

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,lena,lenb,m,max;
char a[2000],b[2000];
int num;
int F[2000][2000];
void lj()
{int H[3][2]={
   {
   1,1},{
   0,1},{
   1,0}};for(int i=1;i<=lena;i++) F[i][0]=i;for(int i=1;i<=lenb;i++) F[0][i]=i;for(int i=1;i<=lena;i++)for(int j=1;j<=lenb;j++){if(a[i]==b[j])F[i][j]=F[i-1][j-1];else{F[i][j]=1e8;for(int k=0;k<3;k++)F[i][j]=min(F[i][j],F[i-H[k][0]][j-H[k][1]]);F[i][j]++;}}
}
int main()
{scanf("%d",&n);while(n--){scanf("%s%s",a+1,b+1);lena=strlen(a+1);lenb=strlen(b+1);lj();printf("%d\n",F[lena][lenb]);}
}