动态规划解编辑距离问题：公式解析与操作含义

编辑距离（Edit Distance）是一个经典的动态规划问题，广泛应用于字符串相似度分析、拼写纠正等领域。它的目标是计算将字符串 $A$ 转换为字符串 $B$ 的最少操作次数，允许的操作包括插入、删除和替换。在本文中，我们不仅会推导编辑距离的动态规划公式，还将深入解释公式如何映射到具体操作。

1. 问题定义

什么是编辑距离？

编辑距离是指将字符串 $A$ 转换为字符串 $B$ 的最小操作次数。假设字符串 $A$ 的长度为 $m$，字符串 $B$ 的长度为 $n$，允许以下操作：

1. 插入：在 $A$ 中插入一个字符。
2. 删除：从 $A$ 中删除一个字符。
3. 替换：将 $A$ 的一个字符替换为另一个字符。

2. 动态规划解法

动态规划定义

我们定义 $dp[i][j]$ 为将字符串 $A[1 \dots i]$ 转换为 $B[1 \dots j]$ 的最小操作次数。基于问题的定义，可以递归地推导出状态转移公式。

初始条件

1. 当 $i = 0$：
   $A$ 是空字符串时，需要插入 $j$ 个字符以匹配 $B[1 \dots j]$，因此：
   $$dp[0][j] = j$$
2. 当 $j = 0$：
   $B$ 是空字符串时，需要删除 $i$ 个字符以匹配 $A[1 \dots i]$，因此：
   $$dp[i][0] = i$$
3. 当 $i = 0$ 且 $j = 0$：
   两个空字符串之间的编辑距离显然是 0：
   $$dp[0][0] = 0$$

状态转移公式

我们分两种情况讨论：

1. 当 $A[i] = B[j]$：
   如果当前字符相同，则无需额外操作，问题可以递归为子问题：

   $$dp[i][j] = dp[i-1][j-1]$$

2. 当 $A[i] \neq B[j]$：
   如果当前字符不同，我们需要选择以下三种操作之一，并选择代价最小的路径：

   • 删除操作：删除 $A[i]$，对应转化为子问题 $dp[i-1][j] + 1$；
   • 插入操作：在 $A$ 中插入一个字符，使其匹配 $B[j]$，对应子问题 $dp[i][j-1] + 1$；
   • 替换操作：将 $A[i]$ 替换为 $B[j]$，对应子问题 $dp[i-1][j-1] + 1$。

综合上述情况，公式为：

3. 动态规划公式中的操作解释（这是理解递推公式的重点！！！）

删除操作：$dp[i-1][j]$

• 操作含义：从 $A[1 \dots i]$ 转换到 $B[1 \dots j]$ 时，选择删除 $A[i]$。
• 剩余问题：此时只需将 $A[1 \dots (i-1)]$ 转换为 $B[1 \dots j]$。
• 成本：删除一个字符的代价是 1，因此：
  $$dp[i][j] = dp[i-1][j] + 1$$

插入操作：$dp[i][j-1]$

• 操作含义：从 $A[1 \dots i]$ 转换到 $B[1 \dots j]$ 时，选择在 $A$ 中插入一个字符，使其匹配 $B[j]$。
• 剩余问题：此时只需将 $A[1 \dots i]$ 转换为 $B[1 \dots (j-1)]$。
• 成本：插入一个字符的代价是 1，因此：
  $$dp[i][j] = dp[i][j-1] + 1$$

替换操作：$dp[i-1][j-1]$

• 操作含义：从 $A[1 \dots i]$ 转换到 $B[1 \dots j]$ 时，选择将 $A[i]$ 替换为 $B[j]$。
• 剩余问题：此时只需将 $A[1 \dots (i-1)]$ 转换为 $B[1 \dots (j-1)]$。
• 成本：替换一个字符的代价是 1，因此：
  $$dp[i][j] = dp[i-1][j-1] + 1$$
• 特殊情况：如果 $A[i] = B[j]$，则无需替换，直接继承之前的状态：
  $$dp[i][j] = dp[i-1][j-1]$$

4. 示例解析

问题描述

我们以将 $A = "horse"$ 转换为 $B = "ros"$ 为例，求解编辑距离。

动态规划表构建

按照上述公式，构建 $dp$ 表如下：

结果解释

表格右下角的值 $dp[5][3] = 3$ 表示从 "horse" 转换为 "ros" 的最小操作次数为 3。

操作路径

通过回溯路径，可以得出操作序列：

1. 删除 $h$："horse" → "orse"；
2. 替换 $o$ 为 $r$："orse" → "rrse"；
3. 删除 $e$："rrse" → "ros"。

python3 代码实现

python
 代码解读
复制代码
def min_edit_distance(A: str, B: str) -> int:
    """
    计算将字符串 A 转换为字符串 B 的最小编辑距离。
    动态规划实现，时间复杂度 O(m * n)，空间复杂度 O(m * n)。

    :param A: 源字符串
    :param B: 目标字符串
    :return: 最小编辑距离
    """
    m, n = len(A), len(B)

    # 初始化 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  # 从空字符串转化为目标字符串所需的插入操作

    # 填充 dp 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:  # 字符匹配，无需操作
                dp[i][j] = dp[i - 1][j - 1]
            else:  # 插入、删除、替换操作中取最小值
                dp[i][j] = 1 + min(
                    dp[i - 1][j],    # 删除
                    dp[i][j - 1],    # 插入
                    dp[i - 1][j - 1] # 替换
                )

    # 返回右下角的结果
    return dp[m][n]


# 示例
A = "horse"
B = "ros"
result = min_edit_distance(A, B)
print(f"将字符串 '{A}' 转换为 '{B}' 的最小编辑距离是: {result}")

5. 总结

动态规划解决编辑距离问题的核心是通过子问题递归，将问题分解为最小操作步骤。我们使用 $dp[i][j]$ 存储每一步的最优解，通过状态转移公式明确地映射到三种基本操作（插入、删除、替换）。理解公式背后的操作含义，不仅有助于解决具体问题，还能加深对动态规划本质的理解。

希望这篇文章能帮助你掌握编辑距离问题的解法与原理！如有疑问或需要进一步的示例分析，欢迎留言讨论！