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

模仿大神写法 https://blog.nowcoder.net/n/e9e179e429324eaa839d296c618f1de5?f=comment

import sys

st1 = input()
st2 = input()
dp = [list(range(len(st2)+1)) for _ in range(len(st1)+1)]
## dp第一列从上到下是st1每个单词从空到st1[:n]需要操作的次数
## dp第一行从左到右是st2每个单词从空到st2[:n]需要操作的次数
## dp第编号i行第编号j列表示从st1[:(i-1)]到st2[:(j-1)]需要操作的次数。
## dp[i][j]如果单独计算难度太大，但dp[i][j]与左侧的dp[i][j-1]、上方的dp[i-1][j]以及左上角的dp[i-1][j-1]有直接关联。
## 对于dp[i][j]，首先判断如果st1的第(i-1)位与st2的第(j-1)位相同，即目前的最后一位相同，
## 那么dp[i][j]与dp[i-1][j-1]应相同，即st1[:(i-1)]到st2[:(j-1)]的操作次数与st1[:(i-2)]到st2[:(j-2)]的操作次数相同。
## 其次，如果st1的第(i-1)位与st2的第(j-1)位不同，则继续计算如下：
## 左侧的dp[i][j-1]多一次添加操作，比如：op -- appl的次数在添加一个'e'，则为op -- apple的次数 
## 或者上方的dp[i-1][j]删除一次操作，比如：o -- apple的次数删除一个'p'，则为op -- apple的次数
## 或者左上角的dp[i-1][j-1]替换一次操作，比如：o -- appl的次数将'p'替换为'e'，则为op -- apple的次数
## dp[i][j]为以上三者的最小值
for i in range(1,len(st1)):
    dp[i][0] = dp[i-1][0]+1
for i in range(1,len(st1)+1):    
    for j in range(1,len(st2)+1):
        if st1[i-1] == st2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            add = dp[i][j-1] + 1
            delete = dp[i-1][j] + 1
            replace = dp[i-1][j-1] + 1
            dp[i][j] = min(add,delete,replace)
print(dp[-1][-1])