动态规划——最小编辑距离问题

def levenshtein(s1,s2):
    edit=[[i+j for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    print(edit)
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                d=0
            else:
                d=1
            edit[i][j]=min(edit[i-1][j]+1,edit[i][j-1]+1,edit[i-1][j-1]+d)
    return edit[len(s1)][len(s2)],edit

参考链接:https://www.jianshu.com/p/9a53f32cf62b