document.write('本题可以使用动态规划的方法来解决，具体思路如下：
给定字符串s1，s2，首先定义一个函数D(i, j) (0≤i≤strlen(s1)，0≤j≤strlen(s2))，用来表示第一
个字符串s1长度为i的子串与第二个字符串s2长度为j的子串的编辑距离。从s1变到s2可以通过如下
三种操作完成：
(1)添加操作。假设已经计算出D(i, j-1)的值(s1[0…i]与s2[0…j-1]的编辑距离)，则D(i, j)=D(i, j1)+1(s1长度为i的字串后面添加s2[j]即可)。
(2)删除操作。假设已经计算出D(i-1,j)的值(s1[0…i-1]到s2[0…j]的编辑距离)，则D(i,j)=D(i1,j)+1(s1长度为i的字串删除最后的字符s1[j]即可)。
(3)替换操作。假设已经计算出D(i-1,j-1)的值(s1[0…i-1]与s2[0…j-1]的编辑距离)，如果
s1[i]=s2[j]，那么D(i,j)=D(i-1,j-1)，如果s1[i]!=s2[j]，那么D(i,j)=D(i-1,j-1)+1(替换s1[i]为s2[j]，
或替换s2[j]为s1[i])。
此外，D(0,j)=j且D(i,0)=i(一个字符串与空字符串的编辑距离为这个字符串的长度)。
由此可以得出如下实现方式：对于给定的字符串s1、s2，定义一个二维数组D，则有以下几种可
能性。
(1)如果i==0，那么D[i,j]=j(0≤j≤strlen(s2))。
(2)如果j==0，那么D[i,j]=i(0≤i≤strlen(s1))。
(3)如果i＞0且j＞0，
(a)如果s1[i]==s2[j]，那么D(i,j)=min{edit(i-1,j)+1, edit(i,j-1)+1, edit(i-1, j-1)}。
(b)如果s1[i]!=s2[j]，那么D(i,j)=min{edit(i-1,j)+1, edit(i,j-1)+1, edit(i-1, j-1)+1}。
通过以上分析可以发现，对于第一个问题可以直接采用上述的方法来解决。对于第二个问题，由
于替换操作是插入或删除操作的两倍，只需要修改如下条件即可：
如果s1[i]!=s2[j]，那么D(i,j)=min{edit(i-1,j)+1, edit(i,j-1)+1, edit(i-1,j-1)+2}。
根据上述分析，给出实现代码如下：
class EditDistance:
def mins(self,a,b,c):
tmp=a if a＜b else b
return tmp if tmp＜c else c
#参数replaceWight用来表示替换操作与插入删除操作相比的倍数
def edit(self,s1,s2,replaceWight):
#两个空串的编辑距离为0
if s1==None and s2==None:
return 0
#如果s1为空串, 那么编辑距离为s2的长度
if s1==None:
return len(s2)
if s2==None:
return len(s1)
len1=len(s1)
len2=len(s2)
#申请二维数组来存储中间的计算结果
D=[([None]*(len2+1)) for i in range(len1+1)]
i=0
while i＜len1+1:
D[i][0]=i
i+=1
i=0
while i＜len2+1:
D[0][i]=i
i+=1
i=1
while i＜len1+1:
j=1
while j＜len2+1:
if list(s1)[i-1]==list(s2)[j-1]:
D[i][j]=self.mins(D[i-1][j]+1, D[i][j-1]+1,\\ D[i-1][j-1])
else:
D[il[j]=min(D[i-1][j]+1 ,D[i][j-1]+1, D[i-1][j-1]\\+replaceWight)
j+=1
i+=1
print "--------------------"
i=0
while i＜len1+1:
j=0
while j＜len2+1:
print D[i][j],
j+=1
print \'\\n\'
i+=1
print "--------------------"
dis=D[len1][len2]
return dis
if __name__ =="__main__":
s1="bciln"
s2="fciling"
ed=EditDistance()
print ”第一问：”
print ”编辑距离：”+str(ed.edit(s1, s2,1))
print ”第二问：”
print ”编辑距离：”+str(ed.edit(s1, s2,2))
程序的运行结果为：
第一问：
-----------------------------------------
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 1 2 3 4 5 6
3 3 2 1 2 3 4 5
4 4 3 2 1 2 3 4
5 5 4 3 2 2 2 3
-----------------------------------------
编辑距离：3
第二问：
-----------------------------------------
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 2 3 4 5 6 7
3 4 3 2 3 4 5 6
4 5 4 3 2 3 4 5
5 6 5 4 3 4 3 4
-----------------------------------------
编辑距离：4
算法性能分析：
这种方法的时间复杂度与空间复杂度都为O(m*n)(其中，m、n分别为两个字符串的长度)。
');