编辑距离（Edit Distance）

题目描述
给定两个单词 word1 和 word2，计算将 word1 转换成 word2 所需的最少操作次数。允许的操作包括：

1. 插入一个字符（成本为1）
2. 删除一个字符（成本为1）
3. 替换一个字符（成本为1）

例如：

• 输入：word1 = "horse", word2 = "ros"
• 输出：3
• 解释：
  horse → rorse（替换 'h' 为 'r'）
  rorse → rose（删除 'r'）
  rose → ros（删除 'e'）

解题过程

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

• i 的范围是 0 到 len(word1)，j 的范围是 0 到 len(word2)。
• 当 i = 0 时，表示 word1 为空，需要插入 j 个字符才能匹配 word2 的前 j 个字符，即 dp[0][j] = j。
• 当 j = 0 时，表示 word2 为空，需要删除 i 个字符才能匹配空字符串，即 dp[i][0] = i。

步骤2：状态转移方程
对于 i > 0 和 j > 0，考虑 word1[i-1] 和 word2[j-1]（因为字符串索引从0开始）：

1. 如果 word1[i-1] == word2[j-1]：
   • 当前字符相同，无需操作，直接继承前一步的结果：dp[i][j] = dp[i-1][j-1]。
2. 如果 word1[i-1] != word2[j-1]：
   • 插入：在 word1 的第 i 个位置后插入 word2[j-1]，则需将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符，再插入一个字符，成本为 dp[i][j-1] + 1。
   • 删除：删除 word1 的第 i 个字符，则需将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符，成本为 dp[i-1][j] + 1。
   • 替换：将 word1[i-1] 替换为 word2[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。

步骤3：初始化与填表

• 初始化一个二维数组 dp，大小为 (len(word1)+1) × (len(word2)+1)。
• 填充第一行和第一列：

  for i in range(len(word1)+1):  
      dp[i][0] = i  
  for j in range(len(word2)+1):  
      dp[0][j] = j  
  

• 按行或按列遍历，根据状态转移方程填充 dp[i][j]。

步骤4：举例演算
以 word1 = "horse", word2 = "ros" 为例：

1. 初始化表：

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

2. 填充过程（仅展示部分关键值）：
   • i=1, j=1：h vs r → 不同，dp[1][1] = min(0, 1, 1) + 1 = 1（替换）。
   • i=2, j=2：o vs o → 相同，dp[2][2] = dp[1][1] = 1。
   • i=5, j=3：e vs s → 不同，dp[5][3] = min(dp[5][2], dp[4][3], dp[4][2]) + 1 = min(3, 2, 2) + 1 = 3。
3. 最终结果：dp[5][3] = 3。

步骤5：复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别为 word1 和 word2 的长度。
• 空间复杂度：可优化至 O(min(m, n))，仅保留当前行和上一行的数据。

总结
编辑距离是动态规划的经典问题，通过分解子问题，逐步比较字符并选择最小成本操作，最终得到全局最优解。