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

import sys

origin = input()
target = input()

dp = [[0 for _ in range(0, len(target)+1)] for _ in range(0, len(origin)+1)]
dp[0] = list(range(0, len(target)+1))
for i in range(0, len(origin) + 1):
    dp[i][0] = i
for i in range(1, len(origin)+1):
    for j in range(1, len(target)+1):
        if target[j-1] == origin[i-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
# print(dp)
print(dp[len(origin)][len(target)])