py3动态规划解法

while 1:
    try:
        s1 = '#'+input()
        s2 = '#'+input()
        m1, m2 = len(s1), len(s2)
        # 用一个占位符表示字符串的开头
        l = [[0 for i in range(m1)] for j in range(m2)]
        for i in range(m2):
            l[i][0] = i
        for j in range(m1):
            l[0][j] = j
        for i in range(1,m2):
            for j in range(1,m1):
                # [i,j]处来自于[i-1,j] [i,j-1] [i-1,j-1]这三个方向走来，
                # l[i-1,j]+1 和l[i,j-1]+1对应着增删，l[i-1][j-1]对应着改，当s1[i]==s2[j]时不用改，否则改
                left = l[i-1][j]+1
                down = l[i][j-1]+1
                left_down = l[i-1][j-1]
                # 当两个点不相同时，左上方加一，否则不用修改
                if s1[j] != s2[i]:
                        left_down += 1
                l[i][j] = min(left, down, left_down)
        print(l[-1][-1])
    except:
        break