我来给你讲解一道经典的动态规划问题：LeetCode 第 72 题「编辑距离」。

题目描述

给你两个单词 word1 和 word2，请计算将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行以下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解题思路

第一步：理解问题本质

编辑距离衡量的是两个字符串的相似程度。我们需要找到一种操作序列，使得转换的代价最小（这里假设每种操作代价都为1）。

第二步：分析子问题结构

考虑两个字符串的前缀：

• 如果我们要将 word1 的前 i 个字符转换为 word2 的前 j 个字符
• 这个问题的解可以通过更小的子问题的解来构建

第三步：定义状态

定义 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作次数。

第四步：找出状态转移方程

考虑最后一步可能进行的操作：

1. 如果两个字符相同（word1[i-1] == word2[j-1]）：

   • 不需要额外操作，直接继承前一个状态的结果
   • dp[i][j] = dp[i-1][j-1]

2. 如果两个字符不同：

   • 插入：在 word1 中插入 word2[j-1]，那么需要 dp[i][j-1] + 1
   • 删除：删除 word1[i-1]，那么需要 dp[i-1][j] + 1
   • 替换：将 word1[i-1] 替换为 word2[j-1]，那么需要 dp[i-1][j-1] + 1
   • 取这三种操作的最小值：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

第五步：确定边界条件

• 当 word1 为空时，需要插入 j 个字符：dp[0][j] = j
• 当 word2 为空时，需要删除 i 个字符：dp[i][0] = i

第六步：构建DP表格

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

初始化表格：

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

逐步填充表格：

• dp[1][1]: 'h' vs 'r' → min(0,1,1)+1 = 1
• dp[1][2]: 'h' vs 'ro' → min(2,1,1)+1 = 2
• 依此类推...

最终表格：

    "" r  o  s
""  0  1  2  3
h   1  1  2  3
o   2  2  1  2
r   3  2  2  2
s   4  3  3  2
e   5  4  4  3  ← 最终结果

第七步：代码实现

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    
    # 创建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 word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i][j-1],    # 插入
                    dp[i-1][j],    # 删除  
                    dp[i-1][j-1]   # 替换
                ) + 1
    
    return dp[m][n]

第八步：复杂度分析

• 时间复杂度：O(m×n)，需要填充 m×n 的DP表
• 空间复杂度：O(m×n)，DP表的大小

第九步：优化空间复杂度

可以优化到 O(min(m,n))，只保留当前行和上一行：

def minDistance_optimized(word1, word2):
    m, n = len(word1), len(word2)
    
    # 让word2是较短的字符串以减少空间
    if m < n:
        return minDistance_optimized(word2, word1)
    
    prev = list(range(n + 1))
    
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = min(prev[j], curr[j-1], prev[j-1]) + 1
        prev = curr
    
    return prev[n]

这个算法在文本比较、拼写检查、DNA序列比对等领域有广泛应用。