矩阵动态规划-编辑距离(edit distance)
编辑距离:
给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。
编辑距离（Edit Distance）问题的动态规划解法是定义一个二维数组 dp[i][j]，其中 i 代表第一个字符串的前 i 个字符，j 代表第二个字符串的前 j 个字符。dp[i][j] 的值就是将第一个字符串的前 i 个字符转换成第二个字符串的前 j 个字符所需要的最小操作次数。
转移方程如下：
- 如果最后一个字符相同，即
word1[i - 1] == word2[j - 1]，则dp[i][j] = dp[i - 1][j - 1]；相当于替换0次操作。 - 如果最后一个字符不同，则需要考虑三种操作：
- 插入操作：
dp[i][j] = dp[i][j - 1] + 1； - 删除操作：
dp[i][j] = dp[i - 1][j] + 1； - 替换操作：
dp[i][j] = dp[i - 1][j - 1] + 1； 最后取这三个操作的最小值
- 插入操作：
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | /**************************************************************** * Description: edit distance * Author: Alex Li * Date: 2024-04-07 22:36:42 * LastEditTime: 2024-04-07 22:38:25 ****************************************************************/ #include <iostream> #include <vector> #include <algorithm> using namespace std; 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]; //相当于替换0次 } else { dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } return dp[m][n]; } int main() { string word1 = "horse"; string word2 = "ros"; cout << "The minimum edit distance is: " << minDistance(word1, word2) << endl; return 0; } |