最小编辑距离 动态规划 python

• m和n的两个字符串，设有以下几种操作：替换（R），插入（I）和删除（D）且都是相同的操作。求转换一个字符串到另一个需要的最少操作数量。这个数量就可以被视为最小编辑距离。如：acd与ace的EditionDistance距离为1，abc与cab的距离为2。

w1=input()
w2=input()
n=len(w1)+1
m=len(w2)+1
dp=[[0]*m for i in range(n)]
for i in range(n):
    dp[i][0]=i
for j in range(m):
    dp[0][j]=j
for i in range(1,n):
    for j in range(1,m):
        if w1[i-1]==w2[j-1]:#字符串下标从零开始
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
print(dp[n-1][m-1])