文档介绍：编辑距离问题
1
题目描述
假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。 我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。 下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。 例如：a=“ABC”,b=“CBCD”,则a与b的编辑距离为2。 你的任务就是：编写一个快速的程序来计算任意两个字符串的编辑距离。
输入
输入包含两行：第一行为字符串A，第二行为字符串B。 字符串的长度不大于10000，且全为字母。
输出
输出只有一行，为编辑距离。
样例输入
ABC 
CBCD
样例输出
2
2
题目分析
乍一看仿佛是搜索，但仔细一想，这道题用搜索是不可能实现的（至少我是这么认为的）。那么我们就要采取新的策略：动态规划。
我们知道，所有的动规问题都是可以分段解决的，那么这道题也是如此。我们可以把长的字符串拆解为短的字符串，一直拆解到只剩下一个字符为止。
3
动态转移方程的推导
判断啊a、b两个字符的编辑距离十分简单：若a=b则编辑距离为0；反之则为1
计算字符a与长度为二的字符串b的编辑距离也不难：首先计算a与b[1]的编辑距离，记为f，再判断a与b[2]是否相同，相同则最终编辑距离为f，不同则为f+1。若b的长度大于2，则该规律依然成立。 注意：这里出现问题了：假如a=‘a’，b=‘aa’，则它们的编辑距离应为1，但通过上述计算得到的结果为0。
4
注意
这里我们要明确一点，对于任意两字符串a、b，它们的编辑距离不可能小于它们的长度之差的绝对值。因为对于三种基本操作，它们对字符串长度的影响为±1（插入和删除）或0（修改）。 举一个例子：a的长度la=9，b的长度lb=15 则a、b的编辑距离m≥abs(la-lb) 即m≥6
5
动态转移方程的推导
解决了上面一个问题，我们继续。 刚才我们已经分析出了两个字符的编辑距离和一个字符与一个字符串的编辑距离，接下来便是两个字符串的编辑距离。
假如a=‘ab’，b=‘cd’，则一眼就可以看出编辑距离m=2。这是没有重复字母的情况下。
但是如果有重复字母呢？
6
动态转移方程的推导
若a=‘ab’，b=‘bc’，则它们的编辑距离m=2
若a=‘ab’，b=‘cb’，则它们的编辑距离m=1
若a=‘ab’，b=‘ab’，则它们的编辑距离m=0
若a=‘abc’，b=‘cba’，则它们的编辑距离m=2
若a=‘abc’，b=‘cab’，则它们的编辑距离m=2
若a=‘abc’，b=‘bac’，则它们的编辑距离m=2
若a=‘abc’，b=‘bcd’，则它们的编辑距离m=2
这有什么规律呢？
7
动态转移方程的推导
我们把上面的几种情况绘成表格：
8
动态转移方程
通过观察表格我们可以发现以下规律：
对于表格f，f[j,k]表示a的前j个字符到b的前k个字符的编辑距离
①若a[j]≠b[k] 则f[j,k]为f[j-1,k-1]、f[j-1,k]、f[j,k-1]三个数中最小数+1
②若a[j]=b[k] 则f[j,k]=f[j-1,k-1]
最终结果为f[la,lb]（la、lb为字符串长度）
9
边界问题
对于方程① 若j=1且k≠1则f[j,k]=f[j,k-1]+1 若k=1且j≠1则f[j,k]=f[j-1,k]+1 若j=1且k=1则f[1,1]=1
对于方程② 若j=1且k≠1则f[j,k]=f[j,k-1] 若k=1且j≠1则f[j,k]=f[j-1,k] 若k=1且j=1则f[1,1]=0
10