C++实现编辑距离计算：小心下标、边界与状态转移！

```cpp #include <iostream> #include <cstring> using namespace std; const int MAXN = 2005; // 定义dp数组，dp[i][j]表示s的前i个字符到t的前j个字符的编辑距离 int dp[MAXN][MAXN]; int main() { char s[MAXN], t[MAXN]; // 读取两个字符串 cin >> s + 1 >> t + 1; int len_s = strlen(s + 1); int len_t = strlen(t + 1); // 初始化边界条件 // 当t为空字符串时，s到t的编辑距离就是删除s的所有字符 for (int i = 0; i <= len_s; i++) { dp[i][0] = i; } // 当s为空字符串时，s到t的编辑距离就是插入t的所有字符 for (int j = 0; j <= len_t; j++) { dp[0][j] = j; } // 状态转移 for (int i = 1; i <= len_s; i++) { for (int j = 1; j <= len_t; j++) { if (s[i] == t[j]) { // 如果当前字符相等，编辑距离不变 dp[i][j] = dp[i - 1][j - 1]; } else { // 否则，取插入、删除、替换操作中的最小值加1 dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1); } } } // 输出结果 cout << dp[len_s][len_t] << endl; return 0; } ``` 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 字符串的下标问题，这里使用 `s + 1` 和 `t + 1` 读取字符串，使得字符串下标从1开始，要注意初始化和状态转移时的下标范围。 2. 边界条件的初始化，`dp[i][0]` 和 `dp[0][j]` 的初始化要正确理解其含义。 3. 状态转移方程的理解和使用，特别是在当前字符不相等时，要正确选择插入、删除、替换操作中的最小值。 ######[AI写代码神器 | 571点数解答 | 2025-08-22 15:51:59]