给定两个字符串S和T，对于T我们允许三种操作：
(1) 在任意位置添加任意字符
(2) 删除存在的任意字符
(3) 修改任意字符
问最少操作多少次可以把字符串T变成S？
例如： S＝ “ABCF” T = “DBFG”
那么我们可以
(1) 把D改为A
(2) 删掉G
(3) 加入C
(2) 删掉G
(3) 加入C
所以答案是3。
分析： 这个最少的操作次数，通常被称之为编辑距离。“编辑距离”一次本身具有最短的意思在里面。因为题目有“最短”这样的关键词，首先我们想到的是BFS。是的，当S的距离为m, T的距离为n的时候，我们可以找到这样的操作次数的界限：
(1) 把T中字符全删了，再添加S的全部字符，操作次数m + n。
(2) 把T中字符删或加成m个，再修改 操作次数最多 |n – m| + m。
虽然，我们找到了这样的上界，BFS从实际角度并不可行，因为搜索空间是指数的，这取决于S中的字符种类——具体的数量级不好估计。
这个问题之所以难，是难在有“添加”“删除”这样的操作，很麻烦。我们试试换个角度理解问题，把它看成字符串对齐的问题，事实上从生物信息学对比基因的角度，我们可以这样理解问题。
给定字符串S和T，我们可以用一种特殊字符促成两个字符串的对齐。我们加的特殊字符是“-”, 我们允许在S和T中任意添加这种特殊字符使得它长度相同，然后让这两个串“对齐”，最终两个串相同位置出现了不同字符，就扣1分，我们要使得这两个串对齐扣分尽量少。
对于例子 我们实际上采取了这样的对齐方式：
12345
ABCF-
DB-FG
注意：如果要对齐，两个“-”相对是没有意义的，所以我们要求不出现这种情况。
那么看一下：
(1) S,T对应位置都是普通字符，相同，则不扣分。 例如位置2，4
(2) S,T对应位置都是普通字符，不同，则扣1分。 例如位置1
(3) S在该位置是特殊字符，T在该位置是普通字符，则扣1分，例如位置5
(4) S在该位置是普通字符，T在该位置是特殊字符，则扣1分，例如位置3
我们来看看扣分项目对应什么？
(1) 不扣分，直接对应
(2) 对应把T中对应位置的字符修改
(3) 对应在T中删除该字符
(4) 对应在T中添加该字符
好了，目标明确，感觉像不像 LCS？我们尝试一下：
设f(i,j)表示S的前i位和T的前j位对齐后的最少扣分。
那我们来看看最后一位，对齐的情况
(1) 必须S[i] == T[j], 这时前i – 1和j – 1位都已经对齐了，这部分肯定要最少扣分。这种情况下最少的扣分是f(i-1,j-1)
(2) 和（1）类似，S[i]≠T[j]，这种情况下最少的扣分是f(i -1, j – 1) + 1
(3) S的前i位和T的前（j – 1）位已经对齐了，这部分扣分也要最少。这种情况下最少的扣分是f(i,j-1) + 1
(4) S的前(i-1)位已经和T的前j位对齐了，这部分扣分要最少。这种情况下最少的扣分是f(i,j-1) + 1
具体f(i,j)取什么值，显然是要看哪种情况的扣分最少。
给定字符串S和T，我们可以用一种特殊字符促成两个字符串的对齐。我们加的特殊字符是“-”, 我们允许在S和T中任意添加这种特殊字符使得它长度相同，然后让这两个串“对齐”，最终两个串相同位置出现了不同字符，就扣1分，我们要使得这两个串对齐扣分尽量少。
对于例子 我们实际上采取了这样的对齐方式：
12345
ABCF-
DB-FG
注意：如果要对齐，两个“-”相对是没有意义的，所以我们要求不出现这种情况。
那么看一下：
(1) S,T对应位置都是普通字符，相同，则不扣分。 例如位置2，4
(2) S,T对应位置都是普通字符，不同，则扣1分。 例如位置1
(3) S在该位置是特殊字符，T在该位置是普通字符，则扣1分，例如位置5
(4) S在该位置是普通字符，T在该位置是特殊字符，则扣1分，例如位置3
我们来看看扣分项目对应什么？
(1) 不扣分，直接对应
(2) 对应把T中对应位置的字符修改
(3) 对应在T中删除该字符
(4) 对应在T中添加该字符
好了，目标明确，感觉像不像 LCS？我们尝试一下：
设f(i,j)表示S的前i位和T的前j位对齐后的最少扣分。
那我们来看看最后一位，对齐的情况
(1) 必须S[i] == T[j], 这时前i – 1和j – 1位都已经对齐了，这部分肯定要最少扣分。这种情况下最少的扣分是f(i-1,j-1)
(2) 和（1）类似，S[i]≠T[j]，这种情况下最少的扣分是f(i -1, j – 1) + 1
(3) S的前i位和T的前（j – 1）位已经对齐了，这部分扣分也要最少。这种情况下最少的扣分是f(i,j-1) + 1
(4) S的前(i-1)位已经和T的前j位对齐了，这部分扣分要最少。这种情况下最少的扣分是f(i,j-1) + 1
具体f(i,j)取什么值，显然是要看哪种情况的扣分最少。
为了方便，我们定义函数same(i,j)表示如果S[i] == T[j]则为0，否则为1。
我们来表示一下递推式：
f(i,j) = min(f(i – 1, j – 1) + same(i,j), f(i – 1,j ) + 1, f(i, j – 1) + 1)
初值是什么？
f(0, j) = j
f(i, 0) = i
这时因为对于S的前0位，我们只能在之前加入“-”，或者说把T全部删掉了。类似地，对于T地前0位，我们只能把S的字符都加进来，别无选择。
注意上述两个式子的重合点 f(0,0) = 0也符合我们的定义，并不矛盾。
时间复杂度？ O(m * n)，空间复杂度？ O(m * n)。同样我们发现到f(i,j)只与本行和上一行有关，可以省掉一维的空间复杂度，从而达到O(n)。
优化后的伪代码：
注意： 我们对于i实际上更新j的顺序是由小到达的，所以我们需要保存“旧的”f[i-1,j – 1]。
我们来表示一下递推式：
f(i,j) = min(f(i – 1, j – 1) + same(i,j), f(i – 1,j ) + 1, f(i, j – 1) + 1)
初值是什么？
f(0, j) = j
f(i, 0) = i
这时因为对于S的前0位，我们只能在之前加入“-”，或者说把T全部删掉了。类似地，对于T地前0位，我们只能把S的字符都加进来，别无选择。
注意上述两个式子的重合点 f(0,0) = 0也符合我们的定义，并不矛盾。
时间复杂度？ O(m * n)，空间复杂度？ O(m * n)。同样我们发现到f(i,j)只与本行和上一行有关，可以省掉一维的空间复杂度，从而达到O(n)。
优化后的伪代码：
for j = 0 to n do f[j] = j endfor for i = 1 to m do last = f[0] f[0] = i for j = 1 to n do temp = f[i,j] f[i,j] = min(last + same(i,j), temp + 1, f[j – 1] + 1) last = f[i,j] endfor endfor
注意： 我们对于i实际上更新j的顺序是由小到达的，所以我们需要保存“旧的”f[i-1,j – 1]。
最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。
输出示例
输入
第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。
输出
输出a和b的编辑距离
输入示例
kitten sitting
输出示例
3
请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。
不同语言如何处理输入输出，请查看下面的语言说明。
1 def array(n): 2 a=[] 3 for i in range(n+1): 4 a.append(0) 5 return a 6 7 def array2(m,n): 8 a=[] 9 for i in range(m+1): 10 a.append(array(n)) 11 return a 12 13 def same(i,j): 14 if a[i-1]==b[j-1]: 15 return 0 16 else: 17 return 1 18 19 a=input() 20 b=input() 21 la=len(a) 22 lb=len(b) 23 f=array2(la,lb) 24 for i in range(la+1): 25 f[i][0]=i 26 for j in range(lb+1): 27 f[0][j]=j 28 for i in range(1,la+1): 29 for j in range(1,lb+1): 30 f[i][j]=min(f[i-1][j-1]+same(i,j),f[i-1][j]+1,f[i][j-1]+1) 31 print(f[la][lb])