编辑距离算法：C++ 实现及开发易错点解析

```cpp #include <iostream> #include <string> #include <vector> using namespace std; // 计算两个字符串的编辑距离 int minDistance(string s, string t) { int m = s.size(); int n = t.size(); // 创建一个二维数组dp来存储子问题的解 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; } // 填充dp数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i - 1] == t[j - 1]) { // 如果当前字符相等，则不需要额外操作 dp[i][j] = dp[i - 1][j - 1]; } else { // 否则，取插入、删除、替换操作中的最小操作数加1 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 s, t; // 读取输入的两个字符串 cin >> s >> t; // 计算并输出编辑距离 cout << minDistance(s, t) << endl; return 0; } ``` 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 注意二维数组`dp`的初始化，特别是第一行和第一列的处理，要正确反映边界情况。 2. 循环填充`dp`数组时，数组的索引要与字符串的索引对应，避免出现越界问题。 3. 在比较字符是否相等时，要注意字符串的索引是从0开始，而`dp`数组的索引是从1开始，避免逻辑错误。 ######[AI写代码神器 | 521点数解答 | 2025-08-20 14:58:56]