题解 | #计算字符串的编辑距离#动态规划

a, b = input(), input()
dp = [[0 for _ in range(len(a) + 1)] for _ in range(len(b) + 1)]
for i in range(len(b) + 1):
    for j in range(len(a) + 1):
        if i == 0:#dp数组第一行初始化赋值
            dp[i][j] = j
            continue
        elif j == 0:#dp数组第一列初始化赋值
            dp[i][j] = i
            continue
        if a[j-1] == b[i-1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
print(dp[len(b)][len(a)])

详细思路见：https://www.bilibili.com/video/BV1sA411B73r/?spm_id_from=333.788.recommend_more_video.-1&vd_source=4b51679533e2205d3f7b87026ed5e2f6