题解 | #计算字符串的编辑距离#

i1 = input()
i2 = input()
m, n = len(i1), len(i2)
# cost add, cost delete, cost remove
ca, cd, cr = 1, 1, 1

dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(n+1):
    dp[0][i] = i
for j in range(m+1):
    dp[j][0] = j
             
for i in range(1,m+1):
    for j in range(1,n+1):
        if i1[i-1] == i2[j-1]:
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j-1]+cr,dp[i][j-1]+ca,dp[i-1][j]+cd)
print(dp[m][n])