编辑距离 内存限制: 256 Mb时间限制: 1000 ms 题目描述 给定两个字符串 s s 与 t t，请计算 s s 到 t t 的编辑距离。所谓编辑距离，就是最少进行多少步修改可以将 s s 变成 t t，每次修改操作可以从以下操作选择一种： 插入一个字符 删除一个字符 替换一个字符 编辑距离是一个很重要的概念，比如： 微信公众号有个规定：已经发表的文章，只能修改 20 20 个字。所以公众号的运营人员需要仔细计算新旧文章的编辑距离。 DNA 是由 actg 四个字母组成的字符串，编辑距离可以规划编辑 DNA 的最佳方案。 输入格式 第一行：一个字符串 s s，由小写英文字符组成 第二行：一个字符串 t t，由小写英文字符组成 输出格式 单个整数：表示两个字符串的编辑距离 数据范围 1 ≤ ∣ s ∣ ≤ 2000 1≤∣s∣≤2000 1 ≤ ∣ t ∣ ≤ 2000 1≤∣t∣≤2000 样例数据 输入: atcg tcga 输出: 2 说明: 删除第一个a，然后在字符串尾部再加一个a 输入: abcdefg gfedcba 输出: 6 用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. 状态转移方程的理解和使用，特别是在当前字符不相等时，要正确选择插入、删除、替换操作中的最小值。 [2025-08-22 15:51:59 | AI写代码神器 | 571点数解答]