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

前辈花了那么大精力研究出来的规律，说实话，不经过学习很难很难解题。但是搞懂规律之后如此简单：

while 1:
	try:
    	str1, str2 = input(), input()
		m, n = len(str1), len(str2)
		dp = [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(m+1):
        	dp[i][0] = i
		for j in range(n+1):
        	dp[0][j] = j
		for i in range(1, m+1):
        	for j in range(1, n+1):
            	if str1[i-1] == str2[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[m][n])
	except:
		break