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

数组规模M*N

s1 = input()
s2 = input()
M = len(s1)
N = len(s2)
dp = [[0 for i in range(N+1)] for j in range(M+1)]
for i in range(M+1):
    for j in range(N+1):
        if i==0:
            dp[0][j] = j
            continue
        if j==0:
            dp[i][0] = i
            continue
        if s1[i-1]==s2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
print(dp[M][N])