当前位置：首页 > news >正文

动态规划经典案例分析之编辑距离

news 2026/4/22 23:10:39

我们先来看题目描述：

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

思路：转换过程中的操作

如果两个单词某个位置的字符相同，可以跳过这一位置，不需要额外的操作。

如果字符不同，则需要进行以下操作之一：

插入一个字符：使 word1 的当前部分匹配 word2 的当前部分。
删除一个字符：使 word1 的当前部分匹配 word2 的当前部分。
替换一个字符：将 word1 的当前字符修改为 word2 的当前字符。

那么，这个时候就得采用动态规划的方式，逐步计算从 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小操作数。

1. 定义

采用二维数组 dp[i][j]，它表示将字符串 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少操作数。

2. 初始状态

当 i = 0（即 word1 为空字符串）时，需要插入 j 个字符才能转成 word2 的前 j 个字符，dp[0][j] = j

当 j = 0（即 word2 为空字符串）时，需要删除 i 个字符才能将 word1 变为空字符串dp[i][0] = i

3. 状态转移分析

对于任意 i >0, j > 0 ，则考虑 word1[i-1] 和 word2[j-1] 是否相同

如果相同（word1[i-1] == word2[j-1]）：无需操作，结果等于转换前 i-1 个字符和 j-1 个字符的结果。dp[i][j] = dp[i-1][j-1]
如果不同（word1[i-1]! = word2[j-1]）：此时就需要选择插入、删除和替换的最优解：

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

dp[i-1][j]：对应删除操作，表示删除word1的当前字符
dp[i][j-1]：对应插入操作，表示在word1的当前追加最后一个字符
dp[i-1][j-1]：对应替换操作，表示将当前字符替换为目标字符。

具体代码如下：

int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; ++i) dp[i][0] = i; for (int j = 0; j <= n; ++j) dp[0][j] = j; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); } } } return dp[m][n]; }