线性动态规划：编辑距离

字数 1368 2025-10-26 09:00:52

线性动态规划：编辑距离

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

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

例如：

输入：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 个字符。
当 j=0 时，表示 word2 为空，需要删除 i 个字符才能变成空串。

2. 状态转移方程
考虑如何从已知状态推导 dp[i][j]：

如果 word1[i-1] == word2[j-1]（当前字符相同）：
不需要操作，直接继承前一步的结果：
dp[i][j] = dp[i-1][j-1]
如果字符不同：
有三种操作可能，取最小值：
1. 插入：在 word1 的前 i 个字符后插入 word2[j-1]，此时 word2 的 j-1 已匹配，故 dp[i][j] = dp[i][j-1] + 1
2. 删除：删除 word1[i-1]，然后匹配 word1 的前 i-1 个字符和 word2 的前 j 个字符，故 dp[i][j] = dp[i-1][j] + 1
3. 替换：将 word1[i-1] 替换为 word2[j-1]，然后匹配剩余部分，故 dp[i][j] = 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[0][j] = j：空串变成长度为 j 的串，需插入 j 次。
dp[i][0] = i：长度为 i 的串变成空串，需删除 i 次。

4. 计算顺序
按 i 从 0 到 m（m = len(word1)），j 从 0 到 n（n = len(word2)）逐行计算。

5. 举例验证
以 word1 = "horse", word2 = "ros" 为例：
初始化 dp 表（行对应 i，列对应 j）：

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

逐步填充：

i=1, j=1：'h'≠'r'，取左、上、左上最小值 min(1,1,0)+1=1 → dp[1][1]=1
i=1, j=2：'h'≠'o'，min(2,1,1)+1=2 → dp[1][2]=2
... 最终 dp[5][3]=3，与例子一致。

6. 复杂度分析

时间复杂度：O(mn)
空间复杂度：可优化至 O(min(m,n))

线性动态规划：编辑距离题目描述给定两个单词 word1 和 word2 ，计算将 word1 转换成 word2 所需的最少操作次数。允许的操作包括：插入一个字符删除一个字符替换一个字符例如：输入：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 个字符。当 j=0 时，表示 word2 为空，需要删除 i 个字符才能变成空串。 2. 状态转移方程考虑如何从已知状态推导 dp[i][j] ：如果 word1[i-1] == word2[j-1] （当前字符相同）：不需要操作，直接继承前一步的结果： dp[i][j] = dp[i-1][j-1] 如果字符不同：有三种操作可能，取最小值：插入：在 word1 的前 i 个字符后插入 word2[j-1] ，此时 word2 的 j-1 已匹配，故 dp[i][j] = dp[i][j-1] + 1 删除：删除 word1[i-1] ，然后匹配 word1 的前 i-1 个字符和 word2 的前 j 个字符，故 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], dp[i-1][j], dp[i-1][j-1]) + 1 3. 初始化边界 dp[0][j] = j ：空串变成长度为 j 的串，需插入 j 次。 dp[i][0] = i ：长度为 i 的串变成空串，需删除 i 次。 4. 计算顺序按 i 从 0 到 m （ m = len(word1) ）， j 从 0 到 n （ n = len(word2) ）逐行计算。 5. 举例验证以 word1 = "horse" , word2 = "ros" 为例：初始化 dp 表（行对应 i ，列对应 j ）：逐步填充： i=1, j=1 ：'h'≠'r'，取左、上、左上最小值 min(1,1,0)+1=1 → dp[1][1]=1 i=1, j=2 ：'h'≠'o'， min(2,1,1)+1=2 → dp[1][2]=2 ... 最终 dp[5][3]=3 ，与例子一致。 6. 复杂度分析时间复杂度：O(mn) 空间复杂度：可优化至 O(min(m,n))