[DnA] dp问题（字符串编辑距离）

方案：

matrix = []
x = []
y = []

def dp(row,col):
if row < 1 or col < 1:
return -1

d = 0
for m in range(1,len(y)):
for n in range(1,len(x)):
#如果当前节点的 行元素 和 列元素 相等,则当前单元格的值为左上角的单元格的值
if x[n] == y[m]:
matrix[m][n] = matrix[m-1][n-1]
#否则在下面三个值里面去一个最小的
else:
first = matrix[m-1][n]+1
second = matrix[m][n-1]+1
third = matrix[m-1][n-1]+1
matrix[m][n] = min(first,second,third)

def getinput(str1,str2):
global x
x = [ele for ele in str1]

global y
y = [ele for ele in str2]

line = []

#构建第一行
for i,ele in enumerate(x):
if ele == y[0]:
tmp = 0
else:
tmp = 1
if i == 0:
line.append(tmp)
else:
line.append(line[i-1]+tmp)
matrix.append(line)


#构建第一列
for j,ele in enumerate(y):
line = [0 for k in range(len(x))]
if ele == x[0]:
tmp = 0
else:
tmp = 1
if j == 0:
line[0] = tmp
else:
line[0] = matrix[j-1][0]+tmp
matrix.append(line)

str1 = input()
str2 = input()
getinput(str1,str2)
dp(1,1)
print(matrix[len(str2)-1][len(str1)-1])