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

# Process input
s, t = input(), input()

# DP
m, n = len(s), len(t)
# - 阶段：s前i个字符，t前j个字符
# - 状态：将t前j个字符序列编辑为和s前i个字符序列相同所需最少操作次数
dp = [[1e10] * (n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
    chs = s[i-1]
    for j in range(1, n+1):
        cht = t[j-1]
        replCost = 0 if chs == cht else 1
        dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+replCost)

# Output
print(dp[m][n])