luoguP2758 编辑距离

你好！作为教练，我非常认同“从暴力到最优”的思考方式。在 NOI 竞赛中，很多复杂的 DP 都是从**搜索（DFS）**原型演变而来的。

下面我将为你演示这道题的三个阶段：从指数级暴力的递归，到消除重复子问题的记忆化搜索，再到最终的递推 DP。

第一阶段：简单暴力版本（纯递归）

思路思考过程： 我们在草稿纸上模拟：对于 $A[i]$ 和 $B[j]$，

• 如果它们相等，就看 $A[i+1...]$ 和 $B[j+1...]$。
• 如果不相等，我们有三条路：
  1. 修改：强行让它们相等，代价 +1。
  2. 删除：把 $A[i]$ 扔了，代价 +1，用 $A[i+1...]$ 去匹配 $B[j...]$。
  3. 插入：在 $A$ 前面补一个跟 $B[j]$ 一样的，代价 +1，用 $A[i...]$ 去匹配 $B[j+1...]$。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 暴力递归函数：计算 A 串从 i 开始和 B 串从 j 开始的编辑距离
int solve(string A, string B, int i, int j) {
    // 边界情况：其中一个串跑完了
    if (i == A.length()) return B.length() - j; // A 完了，B 剩下的全靠插入
    if (j == B.length()) return A.length() - i; // B 完了，A 剩下的全删掉

    // 情况 1：当前字符相等
    if (A[i] == B[j]) {
        return solve(A, B, i + 1, j + 1);
    }

    // 情况 2：字符不等，尝试三种操作取最小值
    int res_replace = solve(A, B, i + 1, j + 1) + 1; // 修改
    int res_delete  = solve(A, B, i + 1, j) + 1;     // 删除
    int res_insert  = solve(A, B, i, j + 1) + 1;     // 插入

    return min({res_replace, res_delete, res_insert});
}

int main() {
    string A, B;
    if (!(cin >> A >> B)) return 0;
    // 暴力版本在长度 > 15 时就会因为复杂度爆炸而超时 (TLE)
    cout << solve(A, B, 0, 0) << endl;
    return 0;
}

• 时间复杂度：$O(3^{\max(N,M)})$。每个状态分裂出 3 个分支，典型的指数级复杂度。
• 空间复杂度：$O(\max(N,M))$，主要是递归系统的栈空间。

第二阶段：记忆化搜索（加个“记事本”）

思路思考过程： 在暴力递归中，我们会发现很多 solve(i, j) 被反复计算。比如：先删 A 再插 A，和先换 A 再保持 A，可能都会走到同一个 $(i, j)$。 我们在纸上画一个 memo[i][j] 表，算过一次就记下来，下次直接取。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int memo[2005][2005];

int solve(const string& A, const string& B, int i, int j) {
    if (i == A.length()) return B.length() - j;
    if (j == B.length()) return A.length() - i;

    // 如果已经算过了，直接返回，不再递归
    if (memo[i][j] != -1) return memo[i][j];

    int res;
    if (A[i] == B[j]) {
        res = solve(A, B, i + 1, j + 1);
    } else {
        res = min({solve(A, B, i + 1, j + 1), 
                   solve(A, B, i + 1, j), 
                   solve(A, B, i, j + 1)}) + 1;
    }

    return memo[i][j] = res; // 记录答案
}

int main() {
    string A, B;
    cin >> A >> B;
    // 初始化记事本为 -1
    for(int i=0; i<2005; ++i) for(int j=0; j<2005; ++j) memo[i][j] = -1;
    cout << solve(A, B, 0, 0) << endl;
    return 0;
}

• 时间复杂度：$O(N \times M)$。每个状态只算一次，表格填满就结束。
• 空间复杂度：$O(N \times M)$。

第三阶段：最优复杂度版本（递推 DP + 滚动数组）

思路思考过程： 递归会有函数调用的开销（NOI 竞赛中需注意）。我们将其改为迭代（递推）。 进一步观察：求 dp[i][j] 只需要 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]。这意味着我不需要存整张表，只需要当前行和上一行。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * NOI 风格的高效写法
 */
int main() {
    // 提升 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    string A, B;
    if (!(cin >> A >> B)) return 0;

    int n = A.length();
    int m = B.length();

    // 空间优化：只用两行，f[curr] 和 f[prev]
    vector<int> f(m + 1);
    vector<int> prev(m + 1);

    // 1. 初始化第 0 行：从空串 A 变成前 j 个 B，需要 j 次插入
    for (int j = 0; j <= m; ++j) prev[j] = j;

    // 2. 逐行递推
    for (int i = 1; i <= n; ++i) {
        f[0] = i; // 每一行的起点：从前 i 个 A 变成空串 B，需要 i 次删除
        for (int j = 1; j <= m; ++j) {
            // 【关键易错点】字符串下标从 0 开始，状态 i 对应 A[i-1]
            if (A[i - 1] == B[j - 1]) {
                f[j] = prev[j - 1]; // 相等则不操作
            } else {
                // 不等则取左（插入）、上（删除）、左上（替换）的最小值 + 1
                // f[j-1] 是左方，prev[j] 是上方，prev[j-1] 是左上方
                f[j] = min({prev[j - 1], prev[j], f[j - 1]}) + 1;
            }
        }
        prev = f; // 完成一行，交换（或者用 i%2 滚动）
    }

    cout << (n == 0 ? m : (m == 0 ? n : prev[m])) << endl;

    return 0;
}

总结分析

1. 复杂度思考过程

• 时间：无论是记忆化搜索还是递推，都是 $O(N \times M)$。对于 $2000 \times 2000$ 的数据规模，总计算次数是 $4 \times 10^6$。在 1.0s 的时限下，这个量级非常轻松。
• 空间：
  • 二维数组版：$2000 \times 2000 \times 4 \text{ bytes} \approx 16 \text{ MB}$。
  • 滚动数组版：$2000 \times 2 \times 4 \text{ bytes} \approx 16 \text{ KB}$。

2. 时间复杂度优化建议

• 常数优化：在内层循环中，std::min({a, b, c}) 在某些老旧编译器上比手写两个 min(a, min(b, c)) 慢一点点。
• 特定场景优化：如果字符串非常大但编辑距离很小（比如 $K \le 100$），可以使用 $O(NK)$ 算法。原理是只计算 DP 表中对角线附近宽度为 $2K$ 的区域，因为距离太远的路径不可能产生最优解。

3. 读题关键词与易错点

• 关键词：看到“三种操作”、“最少次数”且涉及“两个序列”，无脑直接联想 二维 DP。
• 易错点 (1)：下标偏移。dp[i][j] 通常表示长度，取字符时要用 A[i-1]。
• 易错点 (2)：相等不加一。很多同学习惯性地给所有转移都 +1，要牢记：DP 的 +1 代表一次“动作”，如果两个字符本身就相等，我们不需要做任何动作，所以不加 1。

希望这次的完整演进能帮你彻底理解这道经典题！