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

import sys

s1, s2 = sys.stdin.read().strip().splitlines()

dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
for j in range(len(s2) + 1):
    for i in range(len(s1) + 1):
        if i == 0:
            dp[i][j] = j
        elif j == 0:
            dp[i][j] = i
        else:
            dp[i][j] = (
                dp[i - 1][j - 1]
                if s1[i - 1] == s2[j - 1]
                else min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
            )
print(dp[-1][-1])

动态规划

定义状态 dp[i][j] s1的前i个字符和s2的前j个字符的编辑距离--最少编辑操作次数

边界条件 dp[0][0] = 0    dp[0][j]=j dp[i][0] = i

状态转移方程 dp[i+1][j+1] = 1 + min{dp[i][j], dp[i+1][j], dp[i][j+1]}