【来不及刷题之】32、编辑距离（动态规划）

编辑距离（Edit Distance）是指将一个字符串转换成另一个字符串所需的最少操作次数。这些操作包括插入一个字符、删除一个字符和替换一个字符。编辑距离常用于自然语言处理、拼写检查和DNA序列比对等领域。

动态规划是解决编辑距离问题的常用方法。下面我们来看一个示例，通过动态规划求解两个字符串的编辑距离。

def edit_distance(str1 str2):
    m = len(str1)
    n = len(str2)
    
    # 创建一个二维数组dp，用于存储编辑距离
    dp = [[0] * (n + 1) for _ 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][j - 1] dp[i - 1][j]) + 1
    
    return dp[m][n]

在上述代码中，我们首先创建一个二维数组`dp`，用于存储编辑距离。然后，我们初始化第一行和第一列，分别表示将一个字符串转换为空字符串所需的操作次数。接下来，我们使用两个嵌套的循环来遍历字符串的每个字符，并根据字符是否相等来更新`dp`数组。如果两个字符相等，则编辑距离不变；否则，我们可以选择插入、删除或替换一个字符，取最小的操作次数加1。最后，返回`dp[m][n]`，即两个字符串的编辑距离。

下面是一个示例的运行结果：

str1 = kitten
str2 = sitting
print(edit_distance(str1 str2))  # 输出结果为3

在上述示例中，我们将字符串kitten转换成字符串sitting所需的最少操作次数为3，即将k替换为s，将e替换为i，将
替换为g。

通过动态规划求解编辑距离问题，我们可以高效地找到两个字符串之间的最小操作次数。这种方法的时间复杂度为O(mn)，其中m和n分别为两个字符串的长度。因此，动态规划是解决编辑距离问题的一种有效方法。