python版本的，采用动态规划
while True:
    try:
        str1=input()
        str2=input()
        dp=[[x for x in range(len(str1)+1)] for y in range(len(str2)+1)]
        for j in range(1,len(str2)+1):
            dp[j][0]=dp[j-1][0]+1
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                if str1[i-1]==str2[j-1]:
                    dp[j][i]=dp[j-1][i-1]
                else:
                    de=dp[j-1][i-1]+1
                    add=dp[j-1][i]+1
                    re=dp[j][i-1]+1
                    dp[j][i]=min(de,add,re)
        print(dp[-1][-1])
    except:
        break