问题描述：
编辑距离是针对二个字符串的差异程度的量化量测，量测方式是看至少需要多少次处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个(或哪几个)是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。
要求：
给定两个序列，假设可以有插入、替换和删除(单个字符)三种编辑操作，设计算法求出这两个序列的最小编辑距离。
思路：
状态表示：c[i,j]表示将x[1 ~ i]变为y[1 ~ j]的操作次数。
初始化：
c[0][i]如果x初始长度就是0，那么只能用插入操作让它变成y
c[i][0]同样地，如果y的长度是0，那么x只能用删除操作让它变成y
删除：如果X串删除一个字符变为Y串，说明X串1 ~ i-1与1 ~ j字符已经相等，故c[i,j]=c[i-1,j]+1。
增加：
如果X串增加一个字符变为Y串，说明增加字符等于y[j],在填之前1~ i与 1~ j-1已经匹配相等 所以可以理解为a的前i个字母和b的前j-1个字母已经匹配，故c[i,j]=c[i,j-1]+1。
对于增加操作解释：在x[i]后面增加一个字母，x[1 ~ i]和y[1 ~ j]就匹配了，匹配就意味着增加的字符必须是y[j]，同时意味着x[1 ~ i]已经和y[1~j-1]匹配了，那么所有将x[1 ~ i]变成y[1 ~ j - 1]的操作方案的最小步数就是c[i, j - 1]。
修改：把x[i]改成y[j]之后想要x[1 ~ i]与y[ 1~ j]匹配 ，那么修改这一位之前，x[1 ~ ( i-1 )]应该与y[1~ j-1)]匹配 ，此时c[i,j]=c[i-1,j-1]+1。但是如果本来x[i]与y[j]这一位上就相等，那么不用改，即c[i,j]=c[i-1,j-1]+0。
代码：#include
#define N 1010
#include
#include
using namespace std;
int n,m;
char x[N],y[N];
int c[N][N];
int main()
{
scanf("%d%s",&n,x+1);//输入x+1从下标1开始存储
scanf("%d%s",&m,y+1);
for(int i=0;i<=n;i++) c[i][0]=i;
for(int i=0;i<=m;i++) c[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
c[i][j]=min(c[i-1][j]+1,c[i][j-1]+1);
if(x[i]==y[j]) c[i][j]=min(c[i][j],c[i-1][j-1]);
else
c[i][j]=min(c[i][j],c[i-1][j-1]+1);
}
}
printf("最小操作数:%dn",c[n][m]);
return 0;
}
优化后：
#include
#include
#define N 1010
#include
#include
using namespace std;
char x[N],y[N];
int c[N];
int main()
{
while(scanf("%s %s",x,y)){
if(x!=NULL) {
if(strlen(x)==0)
return strlen(y);
}
if(y!=NULL) {
if(strlen(y)==0)
return strlen(x);
}
int n=strlen(x);//在更新a[i][j]时，只会用到左上角a[i-1][j-1]、左侧a[i][j-1]、上侧a[i-1][j] 这三个值
int m=strlen(y);
int c[m+1];
for(int i=0;i
for(int i=1;i
int left_up=c[0];//记录原来二维数组中左上角改的值
c[0]=i;// 更新原来二维数组中左侧插入的值
for(int j=1;j
int up=c[j];//记录原来二维数组上侧删的值c[i-1][j]
if(x[i-1] == y[j-1])
c[j]=left_up;
else{
int temp=min(c[j-1],c[j]);
temp=min(temp,left_up);
c[j]=1+temp;
}
left_up=up;//当前删的值，到下一个字符时已经变成左上角改的了
}
}
printf("最小操作数:%dn",c[m]);
}
return 0;
}
