多序列动态规划：最长公共子序列与编辑距离的深入解析

核心逻辑与数学原理

多序列动态规划的本质是在多维笛卡尔积构成的状态空间中进行拓扑路径搜索。本节聚焦于最长公共子序列（LCS）与编辑距离（Edit Distance），这两类问题展示了在“对齐”与“匹配”过程中的状态演变。

1. 最长公共子序列 (LCS)

给定两个序列 $A$（长度为 $N$）和 $B$（长度为 $M$），求其最长公共子序列的长度。其核心逻辑在于判定当前末尾元素 $A[i]$ 与 $B[j]$ 的对等性：

• 若 $A[i] == B[j]$，则该字符必然属于当前最优公共子序列的末尾，状态直接由前驱 $f[i-1][j-1]$ 步长增长 1 转移而来。
• 若 $A[i] \neq B[j]$，说明 $A[i]$ 和 $B[j]$ 至少有一个是冗余的，最优解必在“抛弃 $A[i]$”与“抛弃 $B[j]$”的子状态中产生。

2. 编辑距离 (Edit Distance)

给定两个字符串 $A$ 和 $B$，计算将 $A$ 转换为 $B$ 所需的最少操作次数（允许插入、删除、替换字符）。编辑距离在几何上可以看作在一张二维网格图上，从左上角 $(0,0)$ 走到右下角 $(N,M)$ 的最短路径问题。每一种操作对应了状态空间中的一个位移向量：

• 删除 $A[i]$：在 $A$ 的维度推进 1，而 $B$ 的维度停滞。向量表示为 $(i-1, j) \to (i, j)$。
• 插入 $B[j]$：在 $B$ 的维度推进 1，而 $A$ 的维度停滞。向量表示为 $(i, j-1) \to (i, j)$。
• 替换字符：双维度同时推进 1。向量表示为 $(i-1, j-1) \to (i, j)$。若 $A[i] == B[j]$，则无需替换，代价为 0；否则代价为 1。

状态设计与算法推导

1. LCS 状态与方程

• 状态设计：$f[i][j]$ 表示序列 $A$ 的前 $i$ 个字符与序列 $B$ 的前 $j$ 个字符的最长公共子序列长度。
• 转移方程：

$$f[i][j] = \begin{cases} f[i-1][j-1] + 1 & \text{if } A[i] == B[j] \\ \max(f[i-1][j], f[i][j-1]) & \text{if } A[i] \neq B[j] \end{cases}$$

• 边界条件：$f[i][0] = f[0][j] = 0$。

2. 编辑距离状态与方程

• 状态设计：$f[i][j]$ 表示将字符串 $A$ 的前 $i$ 个字符转换为字符串 $B$ 的前 $j$ 个字符所需的最少操作次数。
• 转移方程：

$$f[i][j] = \min \begin{cases} f[i-1][j] + 1 & \text{(删除操作)} \\ f[i][j-1] + 1 & \text{(插入操作)} \\ f[i-1][j-1] + \text{cost} & \text{(替换操作)} \end{cases}$$

其中，若 $A[i] == B[j]$ 则 $\text{cost} = 0$，否则 $\text{cost} = 1$。

• 边界条件：
• $f[i][0] = i$：将长度为 $i$ 的字符串全删除变为空串，需 $i$ 次操作。
• $f[0][j] = j$：从空串插入 $j$ 个字符变为 $B$ 的前 $j$ 个字符，需 $j$ 次操作。

C++ 标准源码（NOIP风格）

以下源码在同一程序中实现了朴素的 $O(N \times M)$ 最长公共子序列与编辑距离算法。

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

using namespace std;

const int MAXN = 2005; // 针对 NOIP 传统二维 DP 数据范围
int lcs_f[MAXN][MAXN];
int edit_f[MAXN][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s1, s2;
    if (!(cin >> s1 >> s2)) return 0;

    int n = s1.length();
    int m = s2.length();

    // 为了符合算法习惯，将字符串索引转换为从 1 开始
    string a = " " + s1;
    string b = " " + s2;

    // ==================== 1. 最长公共子序列 (LCS) ====================
    // 边界显式赋值（虽然全局变量默认全 0，但工程规范要求显式体现）
    for (int i = 0; i <= n; ++i) lcs_f[i][0] = 0;
    for (int j = 0; j <= m; ++j) lcs_f[0][j] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) {
                lcs_f[i][j] = lcs_f[i - 1][j - 1] + 1; // 致命踩坑点：此处决不能与后方的 max 混淆
            } else {
                lcs_f[i][j] = max(lcs_f[i - 1][j], lcs_f[i][j - 1]);
            }
        }
    }

    // ==================== 2. 编辑距离 (Edit Distance) ====================
    // 边界初始化：空串转换的代价
    for (int i = 0; i <= n; ++i) edit_f[i][0] = i;
    for (int j = 0; j <= m; ++j) edit_f[0][j] = j;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = (a[i] == b[j]) ? 0 : 1;

            // 三种转换向量取极小值
            int del_op = edit_f[i - 1][j] + 1;
            int ins_op = edit_f[i][j - 1] + 1;
            int rep_op = edit_f[i - 1][j - 1] + cost;

            edit_f[i][j] = min({del_op, ins_op, rep_op});
        }
    }

    cout << "LCS: " << lcs_f[n][m] << "\n";
    cout << "Edit Distance: " << edit_f[n][m] << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 字符串下标与 DP 状态下标错位

• 现象：C++ 中 std::string 的索引从 0 开始到 len-1 结束。若 DP 循环写 for (int i = 1; i <= n; ++i)，内部直接读取 s1[i] 就会引发下标越界（读取了 s1[n]）或者漏掉了 s1[0]。
• 规避手段：建议在考场上采取“补空格法”。读入字符串后，强行在前面拼接一个空格 s = " " + s;。这样可以将原始字符串字符整体后移，使得 s[i] 完美契合状态 $f[i][j]$ 中“前 $i$ 个字符”的物理定义。

2. 编辑距离中忽视 $A[i] == B[j]$ 时的替换代价

• 现象：在计算编辑距离时，选手错误地认为当 $A[i] == B[j]$ 时，整个状态 $f[i][j]$ 直接等于 $f[i-1][j-1]$。从而漏掉了通过“先删除再插入”等其他复合操作在极极端数据下可能产生的更小代价（虽然在常理下直接对齐最优，但在魔改题意、各类操作代价不相等的变型题中，这会导致致命逻辑漏洞）。
• 规避手段：无论当前字符是否相等，都必须让删除、插入、替换三种操作共同参与 min() 算子的运算，仅仅是用 cost = 0 或 1 来调节替换操作的权重。

经典 NOIP/洛谷 真题

1. 洛谷 P2758 编辑距离

• 题意描述：设 $A$ 和 $B$ 是两个字符串。我们要确定将 $A$ 变为 $B$ 所需的最少操作次数。允许的操作有：删除一个字符、插入一个字符、将一个字符改为另一个字符。
• 问题本质与解题思路：标准的二维多序列 DP 模板题。
• 核心思路：严格按照上文推导的编辑距离方程进行状态转移。外层枚举 $i$，内层枚举 $j$，利用三向分支松弛更新 f[i][j]。由于数据范围较小（字符串长度 $\le 2000$），$O(N \times M)$ 的时空复杂度可完美压线通过。

2. 洛谷 P1156 垃圾陷阱

• 题意描述：卡门（一头牛）被关在深 $D$ 的井底。每隔一段时间有一件垃圾掉下来，每个垃圾有掉落时间 $t_i$、吃掉它能维持生命的时间 $f_i$、以及堆叠高度 $h_i$。卡门初始有 10 小时的生命值。求卡门最早跳出井的时刻；若跳不出，求它最长能活多久。
• 问题本质与解题思路：多序列对齐问题的变型（时间轴与高度轴的复合对齐）。垃圾掉落是离散的阶段，必须按时间先对垃圾进行升序排序。
• 状态设计：$f[i][j]$ 表示处理完前 $i$ 个垃圾、当前堆叠高度为 $j$ 时，卡门所持有的最大剩余生命值。
• 核心思路：将垃圾视为阶段。对于第 $i$ 个垃圾，其掉落时间为 $t_i$。首先必须保证上一阶段的生命存量能够活到 $t_i$，即 $f[i-1][j] \ge t_i - t_{i-1}$。在此基础上进行两条路径的决策更新（我为人人型逆推）：

1. 用来堆叠：$f[i][j + h_i] = \max(f[i][j + h_i], f[i-1][j] - (t_i - t_{i-1}))$。若 $j + h_i \ge D$，则可以直接输出 $t_i$ 并终止程序。
2. 用来吃：$f[i][j] = \max(f[i][j], f[i-1][j] - (t_i - t_{i-1}) + f_i)$。 如果所有垃圾遍历完仍无法让高度 $\ge D$，则全局最大存活时间即为高度为 0 状态所能支撑的最大跨度。