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

#原理搞懂了，其实很简单哈。使用动态规划自底向上
#1.比较当前字符不相等时，可通过左边添加一个字符、右上角时为替换当前字符、上边字符
#为删除一个字符。此处不懂结合图表想想，想通很简单哈。
#状态转移方程为：dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i-1][j]+1)
#2.解决此类问题需：
    #a.先绘制二维列表用于记录状态转移值，本质用空间换时间；
    #b.再找出状态转移方程，动态更新二维列表；
def ls(a,b):
    dp = [[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
    for i in range(len(a)+1):
        dp[0][i] = i
    for j in range(len(b)+1):
        dp[j][0] = j
    #状态转移方程：左边添加一个字符，左上角是替换当前字符，上面的是删除当前字符
    for i in range(1,len(b)+1):
        for j in range(1,len(a)+1):
            if b[i-1] != a[j-1]:
                dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i-1][j]+1)
            else:
                dp[i][j] = dp[i-1][j-1]

    return dp

a = input()
b = input()
dp = ls(a,b)
print(dp[len(b)][len(a)])