编辑距离问题

问题描述：设A和B是两个字符串，要用最少的字符操作将字符串A转换为字符串B，这里所说的字符操作包括（1）：删除一个字符；（2）：插入一个字符；（3）：修改一个字符。将A转换为B所用的最少字符操作数称为A到B的编辑距离，记为d[A][B]，d[][]中的A，B指的是A和B的长度，设计一个算法对任给的A，B，计算出d[A][B]。
问题举例：假设A = "fxpimu", B = "xwrs"，则d[6][4]为5。
问题分析：这个问题乍一看好像没什么突破口，这样，我们回忆一下01台阶问题，到达第i个台阶的办法只有两种办法，一个是跨一步到，一个是跨两步到，将这样的分析思路带入到这
道题中，计算出d[A][B]的途径有哪几种，其实就是题目已经告诉的三种：删除，插入，修改字符，我们一一来看：删除其实是d[i-1][j]+1（i-1转换为j-1的编辑距离再加1
，这个1是删除的操作），同理插入可表示为d[i][j-1]+1，那修改如何表示呢？我们想象在进行字符操作后（计算d[][]的过程中），i-1和j-1已经完全相等，那么各给它们
两个后再添加一个字符，那么修改就取决于添加的两个字符相不相等，如果相等d[i][j] = d[i-1][j-1]，如果不相等d[i][j] = d[i-1][j-1]+1（就修改一次）。

import numpy as np
str1 = input()
str2 = input()
inf = 9999999
dp = np.full((len(str1) + 1, len(str2) + 1), inf)
print(dp)
for i in range(0, len(str1)):
    dp[i][0] = i
for j in range(0, len(str2)):
    dp[0][j] = j
for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1))
        else:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1))
print(dp[len(str1)][len(str2)])