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

注意动态规划的时候，dp行下标列下标的含义和字符串对比的长度！

s = input().strip()
t = input().strip()

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
# 初始化
for j in range(len(s)+1):
    dp[0][j] = j
for i in range(len(t)+1):
    dp[i][0] = i

# 遍历
for i in range(1, len(t)+1):
    for j in range(1, len(s)+1):
        dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + (s[j-1]!=t[i-1]))

print(dp[len(t)][len(s)])