一、问题描述
最短编辑距离(Minimum Edit Distance)，也被称为Levenshtein距离，是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如替换、插入、删除）所需要的最少次数。 简单例子： 给定两个单词word1，word2，找到最少的修改操作次数，使得将word1转换成word2，操作包含替换，插入，删除。
1.替换操作：将某个字符替换成另一个字符
2.插入操作：在某两个字符中间插入一个新的字符
3.删除字符：删除某一个字符
例如，word1=‘ssitten’，word2=‘sitting’，其中最短的编辑操作为
将 word1 的第一个‘ s ’删除；将‘ e ’替换成‘ i ’；末尾处插入字符‘ g ’，所以编辑距离为3
二、动态规划
不妨先想一想，两个字符串的最短编辑距离，只需要考虑对其中一个字符串操作即可，所以最短编辑距离的最大值一定不超过两个字符串长度的较大值（只对较短字符串进行替换和插入操作）。 在动态规划思想中，将问题转化成一个个子问题来解决，即如何根据上述三种操作方式推导。定义 F[ i ][ j ] 为字符串1中 1 ~ i 和字符串2 1 ~ j 中的最短编辑距离，将字符串从末尾开始比较有以下递推公式。
1.当两个字符串末尾相同时 （word1 = "intention’, word2 = ’execution‘ ）
此时不需要任何操作 即可
2.当两个字符串末尾不相同时，有以下三种操作。
① 替换操作
直接将 word1 中的末尾字符替换成 word2 中的末尾字符，操作数+1，此时情况为 case1 易理解。
②插入操作
在 word1 的末尾后面插入 word2 的末尾字符，操作数+1，举例说明
例如上述样例 word1=‘ssitten’，word2=‘sitting’ 此时在 word1 末尾加上 ‘ g ’ ，word1 和 word2 此时末尾字符相同，即同上述情况相同有
③ 删除操作
直接删除 word1 末尾的元素，考虑 F[ i-1 ] [ j ]
再考虑初始条件
则递推公式为：
三、代码部分
#include<stdio.h>
#include<string.h>
using namespace std;
#include<iostream>
int f[2001][2001],n;
char s1[10001],s2[10001];
int main()
{
scanf("%s",s1);
scanf("%s",s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=l1-1;i>=0;i--)
s1[i+1]=s1[i];
for(int j=l2-1;j>=0;j--)
s2[j+1]=s2[j];
for(int i=1;i<=l1;i++) f[i][0]=i;
for(int i=1;i<=l2;i++) f[0][i]=i;
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
{
if(s1[i]==s2[j])
f[i][j]=f[i-1][j-1];
else
{
f[i][j]=min(min(f[i-1][j-1]+1,f[i-1][j]+1),f[i][j-1]+1); // 替换 删除 插入
}
}
printf("%d",f[l1][l2]);
return 0;
}
