Time Limit:1000MS Memory Limit:65536K
Description
俄罗斯科学家Vladimir Levenshtein在1965年提出了编辑距离概念。编辑距离，又称Levenshtein距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的三种编辑操作包括插入一个字符、删除一个字符、将一个字符替换成另一个字符。
至今，编辑距离一直在相似句子检索的领域中发挥着不可忽视的作用。
我们不妨来设计一个程序，计算两个字符串的编辑距离。
Input
输入数据的第一行是一个正整数，表示一共有几组数据。
每组数据有两行，每行一个字符串。
* 每个字符串长度不超过1000
* 字符串中只含小写英文字母
Output
对于每组数据，请输出一个整数表示两个字符串的编辑距离。
每个答案占一行。
Sample Input
2
david
vivian
abc
aabbcc
Sample Output
4
3
这题大部分人都不陌生，经典的dp题，对字符串的很多处理都是dp问题，说说解法吧!
dp[i][j]表示从串s1前i位的字符变换到串s2的前j位字符的最小步数；
如果是长度差1的话就直接添加或减少，都需要1步；
如果长度相同时，当s1[i]=s2[j]时，不需要加步骤，直接从dp[i-1][j-1]转移过来；
如果长度不同则需要变换1步，所以从dp[i-1][j-1]加1步即可；
下面是我的代码
#include<cstdio>
#include<iostream>
#include<cstring>
#define min(a,b) (a)>(b)?(b):(a)
#define N 1005
using namespace std;
int dp[N][N];
int DP(char *s1,char *s2)
{
int i,j,len1=strlen(s1),len2=strlen(s2),tem;
for(i=0;i<=len2;i++)
dp[0][i]=i;
for(i=0;i<=len1;i++)
dp[i][0]=i;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
tem=dp[i-1][j-1];
else
tem=dp[i-1][j-1]+1;
tem=min(tem,dp[i][j-1]+1);
tem=min(tem,dp[i-1][j]+1);
dp[i][j]=tem;
}
return dp[len1][len2];
}
int main()
{
int c;
char s1[N],s2[N];
scanf("%d",&c);
getchar();
while(c--)
{
gets(s1);
gets(s2);
printf("%d\n",DP(s1,s2));
}
return 0;
}