动态规划：编辑距离（Edit Distance）问题

一、问题描述

编辑距离（Levenshtein Distance）是衡量两个字符串之间相似程度的一种方法。它定义为：将一个字符串转换成另一个字符串所需的最少编辑操作次数。允许的编辑操作有三种：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

例如，将字符串"horse"转换为"ros"：

1. horse -> rorse (将'h'替换为'r')
2. rorse -> rose (删除第二个'r')
3. rose -> ros (删除'e')
   编辑距离为3。

我们的任务是：给定两个字符串word1和word2，计算它们的最小编辑距离。

二、解题思路分析

这个问题本质上是寻找从word1到word2的最优编辑序列。我们可以尝试用动态规划解决，因为它满足最优子结构和重叠子问题。

关键思路：比较两个字符串的最后字符，然后递归地考虑子问题。

假设word1长度为n，word2长度为m，我们定义dp[i][j]为word1的前i个字符（即word1[0..i-1]）转换成word2的前j个字符（word2[0..j-1]）的最小编辑距离。

三、动态规划解法详解

步骤1：定义状态
创建一个二维数组dp，大小为(n+1) x (m+1)，其中dp[i][j]表示word1的前i个字符与word2的前j个字符之间的最小编辑距离。

为什么维度是n+1和m+1？
因为我们考虑空字符串的情况。dp[0][j]表示从空字符串转换为word2的前j个字符，只能进行j次插入操作。dp[i][0]表示从word1的前i个字符转换为空字符串，只能进行i次删除操作。

步骤2：初始化边界条件

1. dp[0][0] = 0：两个空字符串之间的编辑距离为0
2. dp[i][0] = i：从word1的前i个字符变成空字符串，需要删除i次
3. dp[0][j] = j：从空字符串变成word2的前j个字符，需要插入j次

用例子说明：word1 = "horse"，word2 = "ros"

• dp[0][0] = 0
• dp[1][0] = 1（"h" -> "" 需要删除1次）
• dp[0][1] = 1（"" -> "r" 需要插入1次）

步骤3：状态转移方程（核心）
对于每个dp[i][j]（i>0, j>0），我们需要考虑三种可能的操作，并取最小值：

1. 删除操作：从word1中删除最后一个字符word1[i-1]，然后考虑word1[0..i-2]到word2[0..j-1]的转换

   • 编辑次数 = dp[i-1][j] + 1

2. 插入操作：在word1末尾插入字符word2[j-1]，然后考虑word1[0..i-1]到word2[0..j-2]的转换

   • 编辑次数 = dp[i][j-1] + 1

3. 替换操作：

   • 如果word1[i-1] == word2[j-1]：不需要替换，编辑次数 = dp[i-1][j-1]
   • 如果word1[i-1] != word2[j-1]：需要替换，编辑次数 = dp[i-1][j-1] + 1

综合起来，状态转移方程为：

dp[i][j] = min(
    dp[i-1][j] + 1,     # 删除
    dp[i][j-1] + 1,     # 插入
    dp[i-1][j-1] + (0 if word1[i-1] == word2[j-1] else 1)  # 替换或不替换
)

步骤4：填充顺序
我们需要按行（i从1到n）和列（j从1到m）的顺序填充dp表。因为计算dp[i][j]需要用到dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]，这些值都应该已经计算好了。

四、完整示例演示

以word1 = "horse"，word2 = "ros"为例：

初始化表格（5+1行，3+1列）：

   0 1 2 3  (j)
   "" r o s
0"" 0 1 2 3
1 h 1
2 o 2
3 r 3
4 s 4
5 e 5
(i)

填充过程：

1. i=1, j=1：比较"h"和"r"

   • 删除：dp[0][1]+1 = 1+1 = 2
   • 插入：dp[1][0]+1 = 1+1 = 2
   • 替换：dp[0][0]+1 = 0+1 = 1（"h"≠"r"）
   • dp[1][1] = min(2,2,1) = 1

2. i=1, j=2：比较"h"和"o"

   • 删除：dp[0][2]+1 = 2+1 = 3
   • 插入：dp[1][1]+1 = 1+1 = 2
   • 替换：dp[0][1]+1 = 1+1 = 2
   • dp[1][2] = 2

3. 继续填充，最终表格：

   0 1 2 3
   "" r o s
0"" 0 1 2 3
1 h 1 1 2 3
2 o 2 2 1 2
3 r 3 2 2 2
4 s 4 3 3 2
5 e 5 4 4 3

最终结果：dp[5][3] = 3，与前面的分析一致。

五、时间复杂度与空间复杂度优化

时间复杂度：O(n×m)，需要填充n×m的表格。

空间复杂度优化：

1. 原始：O(n×m)，存储整个dp表
2. 优化1：O(min(n,m))，只存储两行（当前行和上一行），因为计算dp[i][j]只需要上一行的值
3. 优化2：O(min(n,m))，甚至可以用一行，但需要额外的变量保存左上角的值

六、代码实现（Python）

def minDistance(word1: str, word2: str) -> int:
    n, m = len(word1), len(word2)
    
    # 初始化dp数组
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 初始化边界条件
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    
    # 填充dp表
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,      # 删除
                    dp[i][j-1] + 1,      # 插入
                    dp[i-1][j-1] + 1     # 替换
                )
    
    return dp[n][m]

# 测试
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5

空间优化版本：

def minDistance_optimized(word1: str, word2: str) -> int:
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    
    n, m = len(word1), len(word2)
    prev = list(range(m + 1))
    
    for i in range(1, n + 1):
        curr = [i] + [0] * m
        for j in range(1, m + 1):
            if word1[i-1] == word2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
        prev = curr
    
    return prev[m]

七、扩展与应用

1. 编辑路径回溯：修改算法记录每一步的操作，可以重建实际的编辑序列
2. 加权编辑距离：不同操作可以有不同权重
3. 应用场景：
   • 拼写检查与自动更正
   • DNA序列比对（生物信息学）
   • 自然语言处理中的相似度计算
   • 版本控制系统中的差异比较

编辑距离问题是动态规划的经典应用，理解它的状态定义和转移方程，可以帮助解决许多类似的字符串处理问题。