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

'''
替换/插入/删除，不包括交换字符顺序.最少次数
动态规划：需构建bp矩阵
'''
s1=input()
s2=input()
# bp[i][j]表示：由s1的前i个字母，变换为s2的前j个字母，需要的距离（包括0个字母）
bp=[[i for i in range(len(s1)+1)] for j in range(len(s2)+1)]

#bp矩阵的第0行是正确的（由s2的0个字母-->s1的前i个字母，0-->j）
#需要先改正第0列的值（由s1的0个字母-->s2的前j个字母，0-->i）
for i in range(len(bp)):
    bp[i][0]=i

# 更正其他位置的取值，从[1][1]开始
# 看尾字符：
#   尾字符相同(i=j)，则最后一步距离为0，此时的距离等于上一步距离(左上角取值，i-1 j-1);
#   尾字符不同，则有三中方法，选择最小值即可
#   (i-1,j)-->(i,j)、(i,j-1)-->(i,j)、(i-1,j-1)-->(i,j)
for i in range(1,len(s2)+1):
    for j in range(1,len(s1)+1):
        if s2[i-1]==s1[j-1]:
            bp[i][j]=bp[i-1][j-1]
        elif s2[i-1]!=s1[j-1]:
            add=bp[i-1][j]+1
            delete=bp[i][j-1]+1
            replace=bp[i-1][j-1]+1
            bp[i][j]=min(add,delete,replace)

print(bp[len(s2)][len(s1)])
'''
for i in bp:
    print(i)  #8*7
'''