编辑距离Python-动态规划

解题思路:

注意事项:

参考代码:

A = list(input())
B = list(input())
m,n = len(A),len(B)
dp = [[0 for _ in range(n+1)] for __ in range(m+1)]
for i in range(1,m+1): #列生成
    dp[i][0] = i
for i in range(1,n+1):  #行生成
    dp[0][i] = i
diff = 0
for i in range(1,m+1):
    for j in range(1,n+1):
        if A[i-1] == B[j-1]:
            diff = 0
        else:
            diff = 1
        dp[i][j] = min(dp[i-1][j-1]+diff,dp[i-1][j]+1,dp[i][j-1]+1)
# print(dp)
print(dp[m][n])