编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 例如将kitten一字转成sitting： sitten （k->s） sittin （e->i） sitting （->g） 所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。 给出两个字符串a,b，求a和b的编辑距离。 Input 第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。 Output 输出a和b的编辑距离 Input示例 kitten sitting Output示例 3 首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。 假设字符串 a, 共 m 位，从 a[1] 到 a[m] 字符串 b, 共 m 位，从 b[1] 到 b[n] d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[i] 的编辑距离
那么有如下递归规律（a[i] 和 b[j] 分别是字符串 a 和 b 的最后一位）：
当 a[i] 等于 b[j] 时，d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离 当 a[i] 不等于 b[j] 时，d[i][j] 等于如下 3 项的最小值： d[i-1][j] + 1（删除 a[i]）， 比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1 d[i][j-1] + 1（插入 b[j])， 比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1 = fxy -> fa 的编辑距离 + 1 d[i-1][j-1] + 1（将 a[i] 替换为 b[j]）， 比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1
显然可以有如下动态规划公式：
if i == 0 且 j == 0，edit(i, j) = 0 if i == 0 且 j > 0，edit(i, j) = j if i > 0 且j == 0，edit(i, j) = i if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。 代码如下：
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<iostream> #define maxn 1004 using namespace std; int ans[maxn][maxn];//注意s1表示的是列,s2表示的是行 int amongmin(int a,int b,int c) { int cnt=a<b?a:b; return =cnt<c?cnt:c; } int main() { int a,b; int i,j; char s1[maxn]; char s2[maxn]; cin>>s1; cin>>s2; a=strlen(s1); b=strlen(s2); for(i=2;i<=a+2;i++) { //ans[0][i]=s1[i]; ans[1][i-1]=i-2;//初始化edit(i,0)=i; } for(i=2;i<=b+2;i++) { //ans[i][0]=s2[i]; ans[i-1][1]=i-2;//初始化edit(0,j)=j; } for(i=2;i<b+2;i++) for(j=2;j<a+2;j++) { if(s2[i-2]==s1[j-2]) ans[i][j]=amongmin(ans[i-1][j-1],ans[i][j-1]+1,ans[i-1][j]+1); else ans[i][j]=amongmin(ans[i-1][j-1]+1,ans[i][j-1]+1,ans[i-1][j]+1); } cout<<ans[b+1][a+1]; }