区间动态规划例题：编辑距离问题 题目描述 给定两个单词 word1 和 word2，请计算将 word1 转换成 word2 所使用的最少操作次数。你可以对一个单词进行以下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') 解题思路 这是一个经典的区间动态规划问题，但更准确地说，它是一个双序列/双字符串的动态规划问题。我们使用一个二维DP数组 dp[i][j] 来记录子问题的解。 定义状态 定义 dp[i][j] 表示将 word1 的前 i 个字符（即 word1[0...i-1] ）转换为 word2 的前 j 个字符（即 word2[0...j-1] ）所需的最少操作次数。 确定状态转移方程 我们需要考虑如何通过已知的子问题解来构建 dp[i][j] 。操作总是作用于 word1 上。对于 word1 的第 i 个字符（ word1[i-1] ）和 word2 的第 j 个字符（ word2[j-1] ）： 情况一：字符相等（ word1[i-1] == word2[j-1] ） 如果这两个字符已经相等，那么我们不需要对 word1[i-1] 进行任何操作。此时， dp[i][j] 的值就等于将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符所需的最少操作次数。即： dp[i][j] = dp[i-1][j-1] 情况二：字符不相等（ word1[i-1] != word2[j-1] ） 如果这两个字符不相等，我们有三种操作可以选择，我们需要从中找出操作次数最少的那一种： 替换操作 ：将 word1[i-1] 替换为 word2[j-1] 。替换后， word1 的第 i 个字符就和 word2 的第 j 个字符匹配上了。那么，我们只需要考虑将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符。这次替换操作算作一次操作。所以， dp[i][j] = dp[i-1][j-1] + 1 。 删除操作 ：将 word1[i-1] 这个字符删除。删除后，我们需要考虑的是将 word1 的前 i-1 个字符（因为第 i 个已经被删了）转换为 word2 的前 j 个字符。这次删除操作算作一次操作。所以， dp[i][j] = dp[i-1][j] + 1 。 插入操作 ：在 word1 的第 i 个位置（即当前字符之后）插入一个字符 word2[j-1] 。插入后， word2 的第 j 个字符就被匹配上了（可以理解为新插入的字符匹配上了），但 word1 的第 i 个字符（原字符）还没有被匹配。所以，我们接下来需要考虑的是将 word1 的前 i 个字符（原字符都还在）转换为 word2 的前 j-1 个字符（因为新插入的字符已经匹配了 word2 的第 j 个字符）。这次插入操作算作一次操作。所以， dp[i][j] = dp[i][j-1] + 1 。 我们需要在这三种可能的操作中，选择一种使得总操作次数最少的。因此，状态转移方程为： dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 初始化边界条件 我们需要考虑空字符串的情况，这是动态规划的基准情况。 dp[0][0] ：将空字符串 "" 转换为空字符串 "" ，不需要任何操作。所以 dp[0][0] = 0 。 dp[i][0] ：将 word1 的前 i 个字符转换为空字符串 "" 。唯一的办法是执行 i 次删除操作（删除所有字符）。所以 dp[i][0] = i 。 dp[0][j] ：将空字符串 "" 转换为 word2 的前 j 个字符。唯一的办法是执行 j 次插入操作（插入所有字符）。所以 dp[0][j] = j 。 计算顺序 根据状态转移方程， dp[i][j] 依赖于其左方 ( dp[i][j-1] )、上方 ( dp[i-1][j] ) 和左上方 ( dp[i-1][j-1] ) 的值。因此，我们应该使用双重循环，外层循环 i 从 0 到 len(word1) ，内层循环 j 从 0 到 len(word2) ，逐个计算。 最终结果 最终， dp[len(word1)][len(word2)] 就是将整个 word1 转换为整个 word2 所需的最少操作次数。 完整计算过程（以 word1="horse", word2="ros" 为例） 初始化一个 (5+1) x (3+1) 的DP表，即 6x4 的表格。 填充边界： dp[0][0] = 0 第一列 dp[i][0] = i ： [0, 1, 2, 3, 4, 5] 第一行 dp[0][j] = j ： [0, 1, 2, 3] | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | | | | | i=2 (o) | 2 | | | | | i=3 (r) | 3 | | | | | i=4 (s) | 4 | | | | | i=5 (e) | 5 | | | | 按行依次计算： i=1, j=1 ：比较 h 和 r ，不相等。 dp[1][1] = min(dp[0][0], dp[0][1], dp[1][0]) + 1 = min(0, 1, 1) + 1 = 0 + 1 = 1 (替换) i=1, j=2 ：比较 h 和 o ，不相等。 dp[1][2] = min(dp[0][1], dp[0][2], dp[1][1]) + 1 = min(1, 2, 1) + 1 = 1 + 1 = 2 (替换或删除+插入) i=1, j=3 ：比较 h 和 s ，不相等。 dp[1][3] = min(dp[0][2], dp[0][3], dp[1][2]) + 1 = min(2, 3, 2) + 1 = 2 + 1 = 3 | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | 1 | 2 | 3 | | i=2 (o) | 2 | | | | | i=3 (r) | 3 | | | | | i=4 (s) | 4 | | | | | i=5 (e) | 5 | | | | i=2, j=1 ：比较 o 和 r ，不相等。 dp[2][1] = min(dp[1][0], dp[1][1], dp[2][0]) + 1 = min(1, 1, 2) + 1 = 1 + 1 = 2 i=2, j=2 ：比较 o 和 o ， 相等 。 dp[2][2] = dp[1][1] = 1 (无需操作) i=2, j=3 ：比较 o 和 s ，不相等。 dp[2][3] = min(dp[1][2], dp[1][3], dp[2][2]) + 1 = min(2, 3, 1) + 1 = 1 + 1 = 2 | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | 1 | 2 | 3 | | i=2 (o) | 2 | 2 | 1 | 2 | | i=3 (r) | 3 | | | | | i=4 (s) | 4 | | | | | i=5 (e) | 5 | | | | i=3, j=1 ：比较 r 和 r ， 相等 。 dp[3][1] = dp[2][0] = 2 i=3, j=2 ：比较 r 和 o ，不相等。 dp[3][2] = min(dp[2][1], dp[2][2], dp[3][1]) + 1 = min(2, 1, 2) + 1 = 1 + 1 = 2 i=3, j=3 ：比较 r 和 s ，不相等。 dp[3][3] = min(dp[2][2], dp[2][3], dp[3][2]) + 1 = min(1, 2, 2) + 1 = 1 + 1 = 2 | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | 1 | 2 | 3 | | i=2 (o) | 2 | 2 | 1 | 2 | | i=3 (r) | 3 | 2 | 2 | 2 | | i=4 (s) | 4 | | | | | i=5 (e) | 5 | | | | i=4, j=1 ：比较 s 和 r ，不相等。 dp[4][1] = min(dp[3][0], dp[3][1], dp[4][0]) + 1 = min(3, 2, 4) + 1 = 2 + 1 = 3 i=4, j=2 ：比较 s 和 o ，不相等。 dp[4][2] = min(dp[3][1], dp[3][2], dp[4][1]) + 1 = min(2, 2, 3) + 1 = 2 + 1 = 3 i=4, j=3 ：比较 s 和 s ， 相等 。 dp[4][3] = dp[3][2] = 2 | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | 1 | 2 | 3 | | i=2 (o) | 2 | 2 | 1 | 2 | | i=3 (r) | 3 | 2 | 2 | 2 | | i=4 (s) | 4 | 3 | 3 | 2 | | i=5 (e) | 5 | | | | i=5, j=1 ：比较 e 和 r ，不相等。 dp[5][1] = min(dp[4][0], dp[4][1], dp[5][0]) + 1 = min(4, 3, 5) + 1 = 3 + 1 = 4 i=5, j=2 ：比较 e 和 o ，不相等。 dp[5][2] = min(dp[4][1], dp[4][2], dp[5][1]) + 1 = min(3, 3, 4) + 1 = 3 + 1 = 4 i=5, j=3 ：比较 e 和 s ，不相等。 dp[5][3] = min(dp[4][2], dp[4][3], dp[5][2]) + 1 = min(3, 2, 4) + 1 = 2 + 1 = 3 | | j=0 | j=1 (r) | j=2 (o) | j=3 (s) | | :---- | :-- | :------ | :------ | :------ | | i=0 | 0 | 1 | 2 | 3 | | i=1 (h) | 1 | 1 | 2 | 3 | | i=2 (o) | 2 | 2 | 1 | 2 | | i=3 (r) | 3 | 2 | 2 | 2 | | i=4 (s) | 4 | 3 | 3 | 2 | | i=5 (e) | 5 | 4 | 4 | 3 | 最终结果 ： dp[5][3] = 3 ，与示例输出一致。 通过这个逐步推导的过程，我们可以清晰地看到如何将一个大问题分解为相互关联的子问题，并通过填表的方式自底向上地解决它们，最终得到整个问题的最优解。