区间动态规划例题：编辑距离问题

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

1. 插入一个字符（成本为 1）
2. 删除一个字符（成本为 1）
3. 替换一个字符（成本为 1，若字符相同则成本为 0）

例如：

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

解题思路

1. 定义状态

   • 设 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小操作次数。
   • 初始状态：dp[0][j] = j（空串变成长度为 j 的字符串需 j 次插入），dp[i][0] = i（长度为 i 的字符串变成空串需 i 次删除）。

2. 状态转移方程

   • 如果 word1[i-1] == word2[j-1]：
     • 当前字符相同，无需操作，继承前一步结果：dp[i][j] = dp[i-1][j-1]
   • 如果字符不同：
     • 插入：在 word1 的前 i 个字符后插入 word2[j-1]，则 dp[i][j] = dp[i][j-1] + 1
     • 删除：删除 word1[i-1]，则 dp[i][j] = dp[i-1][j] + 1
     • 替换：将 word1[i-1] 替换为 word2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
     • 取三者最小值：

       dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)  
       

3. 遍历顺序

   • 外层循环遍历 i（1 → len(word1)），内层循环遍历 j（1 → len(word2)）。

4. 最终答案

   • dp[len(word1)][len(word2)]

详细推导示例（word1="horse", word2="ros"）

1. 初始化 dp 表：

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

2. 填充过程（节选关键步骤）：

   • i=1, j=1（h→r）：不同，dp[1][1] = min(dp[1][0]+1, dp[0][1]+1, dp[0][0]+1) = min(2, 2, 1) = 1
   • i=2, j=2（ho→ro）：o=o，相同，dp[2][2] = dp[1][1] = 1
   • i=5, j=3（horse→ros）：
     • 最后字符 e≠s，需比较：
       • 插入：dp[5][2]+1 = 3+1=4
       • 删除：dp[4][3]+1 = 2+1=3
       • 替换：dp[4][2]+1 = 2+1=3
     • 取最小值 3

3. 最终结果：dp[5][3] = 3

总结

• 编辑距离是区间动态规划的经典问题，通过分解子问题（前缀匹配）避免重复计算。
• 关键点：理解插入、删除、替换操作对应的状态转移来源。
• 时间复杂度：O(mn)，空间复杂度可优化至 O(min(m,n))。