LIS、LCS与编辑距离

前言

上一篇 背包问题 里，状态是”容量”——一个一维的数字。这一篇要处理的状态变成了两个序列的位置，状态从一维升到二维。

为什么要比较两个序列？比如你要判断两篇论文是不是抄袭，就需要衡量它们的”相似度”——最长的公共子序列有多长？把一个改成另一个最少要改几处？这些都是经典的序列比较问题。

即使是单个序列，也有一个重要问题：最长递增子序列（LIS）有多长？它不仅是 DP 入门经典题，还能用贪心+二分优化到 $O(N \log N)$——这个技巧在其他题目中也经常出现。

问题的本质

LIS：从哪里截断最划算？

给定序列 $A = [2, 3, 1, 6, 4, 5]$，找一个最长的子序列（不要求连续），使得元素严格递增。

朴素的 DP：$dp[i]$ = 以 $A[i]$ 结尾的 LIS 长度。转移：$dp[i] = \max_{j < i, A[j] < A[i]}(dp[j] + 1)$。$O(N^2)$。

但有一个更聪明的做法——贪心 + 二分。维护一个数组 $d$，$d[k]$ = 长度为 $k$ 的递增子序列末尾元素的最小值。为什么存最小值？因为末尾越小，后面的元素越容易接上去。每次新来一个元素 $x$，用 lower_bound 找到 $d$ 中第一个 $\ge x$ 的位置替换。如果 $x$ 比 $d$ 中所有元素都大，就追加——LIS 长度 +1。

LCS：两个序列的”交集”

LIS 是一个序列和自己比。LCS（Longest Common Subsequence）是两个序列互相比较——$S$ 和 $T$ 的最长公共子序列有多长？

关键观察：比较 $S[i]$ 和 $T[j]$ 时，只有两种情况——相同或不同。如果 $S[i] = T[j]$，这对字符可以匹配，LCS 长度加 1。如果不同，要么跳过 $S[i]$，要么跳过 $T[j]$，取较大值。

编辑距离：从 $S$ 变成 $T$ 最少几步？

编辑距离在 LCS 的基础上多了一种操作——替换。除了”跳过 $S[i]$“（删除）和”跳过 $T[j]$“（插入），还可以把 $S[i]$ 改成 $T[j]$（替换，花费 1）。

理论 + 代码

LIS：贪心 + 二分 $O(N \log N)$

#include <algorithm>
using namespace std;

int LIS(int A[], int N) {
    int d[500009], len = 0;            // d[k] = 长度为 k+1 的 LIS 末尾最小值
    for (int i = 0; i < N; i++) {
        int pos = lower_bound(d, d + len, A[i]) - d; // ① 找第一个 >= A[i] 的位置
        d[pos] = A[i];                 // ② 替换
        if (pos == len) len++;         // ③ 比所有都大，LIS 延长
    }
    return len;
}

逐行解析：

• ① lower_bound(d, d+len, A[i]) 找到 $d$ 中第一个 $\ge A[i]$ 的位置。这意味着 $A[i]$ 可以接在长度为 $pos$ 的子序列后面。
• ② 把 $d[pos]$ 更新为 $A[i]$——保持”末尾最小”。
• ③ 如果 $pos = len$，说明 $A[i]$ 比所有已有末尾都大，LIS 长度可以 +1。

模拟：$A = [2, 3, 1, 6, 4, 5]$。

步骤	A[i]	d 的变化	len
1	2	d=[2]	1
2	3	d=[2,3]（追加）	2
3	1	d=[1,3]（替换 d[0]）	2
4	6	d=[1,3,6]（追加）	3
5	4	d=[1,3,4]（替换 d[2]）	3
6	5	d=[1,3,4,5]（追加）	4

LIS 长度 = 4。对应子序列 $[2, 3, 4, 5]$（或 $[1, 3, 4, 5]$）。✓

注意：$d$ 数组本身不是 LIS，它只是辅助计算长度的工具。要还原具体方案需要额外处理。

LCS：二维 DP

状态：$dp[i][j]$ = $S$ 的前 $i$ 个字符和 $T$ 的前 $j$ 个字符的 LCS 长度。

转移：

$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & S[i] = T[j] \\ \max(dp[i-1][j],\ dp[i][j-1]) & S[i] \ne T[j] \end{cases}$

为什么？如果 $S[i] = T[j]$，这对字符一定在最优解中被匹配——不匹配只会浪费。如果不同，那要么不选 $S[i]$（跳过），要么不选 $T[j]$（跳过），取较大值。

int dp[2009][2009];
// S 长度 N，T 长度 M
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++) {
        if (S[i-1] == T[j-1])
            dp[i][j] = dp[i-1][j-1] + 1;    // ① 匹配
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // ② 跳过
    }
// 答案 = dp[N][M]

模拟：$S$ = “mynavi”，$T$ = “monday”。

		m	o	n	d	a	y
	0	0	0	0	0	0	0
m	0	1	1	1	1	1	1
y	0	1	1	1	1	1	2
n	0	1	1	2	2	2	2
a	0	1	1	2	2	3	3
v	0	1	1	2	2	3	3
i	0	1	1	2	2	3	3

LCS = 3，对应 “mna”。✓

编辑距离

状态：$dp[i][j]$ = 把 $S$ 的前 $i$ 个字符变成 $T$ 的前 $j$ 个字符的最少操作数。

转移：

$dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & \text{删除 } S[i] \\ dp[i][j-1] + 1 & \text{插入 } T[j] \\ dp[i-1][j-1] + (S[i] \ne T[j]) & \text{替换或保留} \end{cases}$

初始值：$dp[0][j] = j$（空串变成长度 $j$ 需要插入 $j$ 次），$dp[i][0] = i$（删除 $i$ 次）。

int dp[2009][2009];
// 初始化
for (int i = 0; i <= N; i++) dp[i][0] = i;  // 全删
for (int j = 0; j <= M; j++) dp[0][j] = j;  // 全插

for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++) {
        int cost = (S[i-1] != T[j-1]) ? 1 : 0;
        dp[i][j] = min({dp[i-1][j] + 1,      // ① 删除
                        dp[i][j-1] + 1,       // ② 插入
                        dp[i-1][j-1] + cost}); // ③ 替换/保留
    }
// 答案 = dp[N][M]

模拟：$S$ = “abc”，$T$ = “bdf”。

		b	d	f
	0	1	2	3
a	1	1	2	3
b	2	1	2	3
c	3	2	2	3

编辑距离 = 3。操作：删除 a（abc→bc），替换 c→d（bc→bd），替换 d→f 不对…实际操作：删除 a，替换 c→d（ab→bd），替换/插入 f。或者：替换 a→b（abc→bbc），替换 b→d（bbc→dbc），替换 c→f（dbc→dbf），再…不对。最简单的理解：$dp[3][3] = 3$ 来自 $dp[2][2]+1$（替换 c→f），$dp[2][2] = 2$ 来自 $dp[1][1]+1$（替换 b→d），$dp[1][1] = 1$ 来自 $dp[0][0]+1$（替换 a→b）。三次替换。✓

例题

例题 1：TB A24 — LIS

题目：给定长度 $N$ 的数组 $A$，求最长递增子序列的长度。

数据范围：$1 \le N \le 10^5$

—— AtCoder Tessoku Book A24

分析：$N = 10^5$，$O(N^2)$ 的朴素 DP 会超时。必须用贪心 + 二分 $O(N \log N)$。

输入样例：

6
2 3 1 6 4 5

输出：4

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int d[500009];

int main() {
    int N;
    scanf("%d", &N);
    int len = 0;
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        int pos = lower_bound(d, d + len, a) - d; // ① 二分查找
        d[pos] = a;                                // ② 替换末尾
        if (pos == len) len++;                     // ③ LIS 延长
    }
    printf("%d\n", len);
}

逐行解析：

• ① lower_bound 在 $O(\log N)$ 内找到 $d$ 中第一个 $\ge a$ 的位置。
• ② 用更小的 $a$ 替换 $d[pos]$，保持”末尾尽可能小”。
• ③ 如果 $a$ 比所有 $d$ 中的元素都大，说明 LIS 可以变长。

---

例题 2：TB A20 — LCS

题目：给定字符串 $S$ 和 $T$，求最长公共子序列的长度。

数据范围：$|S|, |T| \le 2000$

—— AtCoder Tessoku Book A20

分析：标准二维 DP。$dp[i][j]$ = $S$ 前 $i$ 个和 $T$ 前 $j$ 个的 LCS。

输入样例：

mynavi
monday

输出：3

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[2009][2009];

int main() {
    char S[2009], T[2009];
    scanf("%s%s", S, T);
    int N = strlen(S), M = strlen(T);

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) {
            if (S[i-1] == T[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;       // ① 字符相同，匹配
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // ② 不同，跳过一边
        }
    printf("%d\n", dp[N][M]);
}

逐行解析：

• ① $S[i-1] = T[j-1]$ 时，这对字符一定被使用（不使用只会让 LCS 更短），所以 LCS 长度 +1。
• ② 字符不同时，要么跳过 $S[i-1]$（看 $dp[i-1][j]$），要么跳过 $T[j-1]$（看 $dp[i][j-1]$），取较大值。
• 复杂度 $O(NM) = O(4 \times 10^6)$，1 秒内可跑完。

---

例题 3：TB B20 — Edit Distance

题目：给定字符串 $S$ 和 $T$，用插入、删除、替换三种操作把 $S$ 变成 $T$，最少需要几步？

数据范围：$|S|, |T| \le 2000$

—— AtCoder Tessoku Book B20

分析：教材 4.5 节的核心例题。三维操作对应三种转移：删除、插入、替换/保留。

输入样例：

tokyo
kyoto

输出：4

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[2009][2009];

int main() {
    char S[2009], T[2009];
    scanf("%s%s", S, T);
    int N = strlen(S), M = strlen(T);

    // ① 初始化：空串变成长度 j 需插入 j 次
    for (int i = 0; i <= N; i++) dp[i][0] = i;
    for (int j = 0; j <= M; j++) dp[0][j] = j;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) {
            int cost = (S[i-1] != T[j-1]) ? 1 : 0;
            dp[i][j] = min({dp[i-1][j] + 1,       // ② 删除 S[i-1]
                            dp[i][j-1] + 1,        // ③ 插入 T[j-1]
                            dp[i-1][j-1] + cost}); // ④ 替换(若不同) 或 保留(若相同)
        }
    printf("%d\n", dp[N][M]);
}

逐行解析：

• ① 边界：$dp[i][0] = i$（把 $S$ 的前 $i$ 个字符全删），$dp[0][j] = j$（往空串插入 $j$ 个字符）。
• ② 删除 $S[i-1]$：操作数 +1，$S$ 少处理一个字符，$T$ 不变。
• ③ 插入 $T[j-1]$：操作数 +1，$S$ 不变，$T$ 多匹配一个字符。
• ④ 如果 $S[i-1] = T[j-1]$，$cost=0$，直接保留，不花操作。如果不同，$cost=1$，替换一次。

---

例题 4：T90 060 — Chimera（★5，先增后减子序列）

题目：长度 $N$ 的数组 $A$。找一个子序列，使得先严格递增再严格递减（增减转折点 $K$ 可以在任意位置），求最大长度。

数据范围：$1 \le N \le 3 \times 10^5$

—— AtCoder Typical 90 060

分析：对每个位置 $i$，分别计算以 $A[i]$ 结尾的正向 LIS 长度 $L[i]$，和以 $A[i]$ 开头的反向 LIS（即递减子序列）长度 $R[i]$。答案就是 $\max_i(L[i] + R[i] - 1)$（$A[i]$ 被算了两次，减 1）。

正反各做一次贪心+二分 LIS，总时间 $O(N \log N)$。

输入样例：

6
1 2 3 3 2 1

输出：5

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int A[300009], L[300009], R[300009];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    // ① 正向 LIS：L[i] = 以 A[i] 结尾的 LIS 长度
    int d[300009], len = 0;
    for (int i = 0; i < N; i++) {
        int pos = lower_bound(d, d + len, A[i]) - d;
        d[pos] = A[i];
        if (pos == len) len++;
        L[i] = pos + 1;  // 长度 = 下标 + 1
    }

    // ② 反向 LIS：R[i] = 以 A[i] 开头的递减子序列长度
    // 等价于对反转数组做 LIS，或者对原数组求"严格递减"= 对 (-A) 做 LIS
    len = 0;
    for (int i = N - 1; i >= 0; i--) {
        int pos = lower_bound(d, d + len, A[i]) - d;
        d[pos] = A[i];
        if (pos == len) len++;
        R[i] = pos + 1;
    }

    // ③ 枚举每个转折点
    int ans = 0;
    for (int i = 0; i < N; i++)
        ans = max(ans, L[i] + R[i] - 1); // ④ A[i] 被两边各算了一次
    printf("%d\n", ans);
}

逐行解析：

• ① 正向扫描，$L[i]$ 记录以 $A[i]$ 结尾的 LIS 长度。注意 pos + 1 是因为 pos 是 0-indexed 的。
• ② 反向扫描，等价于从右到左求”递增”，也就是从左到右看是”递减”。$R[i]$ = 以 $A[i]$ 为开头的最长递减子序列长度。
• ④ 位置 $i$ 同时属于递增部分（被 $L[i]$ 统计）和递减部分（被 $R[i]$ 统计），所以减 1。

模拟：$A = [1, 2, 3, 3, 2, 1]$。

正向 LIS：$L = [1, 2, 3, 3, 2, 1]$。 反向 LIS：$R = [1, 2, 3, 3, 2, 1]$。

$L[i] + R[i] - 1$：$[1, 3, 5, 5, 3, 1]$。最大值 5（位置 2 或 3）。✓

---

例题 5：TB B21 — Longest Subpalindrome（最长回文子序列）

题目：长度 $N$ 的字符串 $S$，求最长回文子序列的长度。

数据范围：$1 \le N \le 1000$

—— AtCoder Tessoku Book B21

分析：教材 4.6 节讲解的区间 DP。状态 $dp[l][r]$ = 子串 $S[l \ldots r]$ 中的最长回文子序列长度。

转移：

• 如果 $S[l] = S[r]$：$dp[l][r] = dp[l+1][r-1] + 2$（两端匹配，中间继续）
• 如果 $S[l] \ne S[r]$：$dp[l][r] = \max(dp[l+1][r],\ dp[l][r-1])$（去掉一端）

初始值：$dp[i][i] = 1$（单个字符），$dp[i][i+1] = 2$（如果相邻两字符相同）或 $1$。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[1009][1009];

int main() {
    int N;
    char S[1009];
    scanf("%d%s", &N, S);

    // ① 长度 1
    for (int i = 0; i < N; i++) dp[i][i] = 1;
    // ② 长度 2
    for (int i = 0; i < N - 1; i++)
        dp[i][i+1] = (S[i] == S[i+1]) ? 2 : 1;

    // ③ 按区间长度递增枚举
    for (int len = 2; len < N; len++)
        for (int l = 0; l + len < N; l++) {
            int r = l + len;
            if (S[l] == S[r])
                dp[l][r] = dp[l+1][r-1] + 2;    // ④ 两端匹配
            else
                dp[l][r] = max(dp[l+1][r], dp[l][r-1]); // ⑤ 去掉一端
        }
    printf("%d\n", dp[0][N-1]);
}

逐行解析：

• ①② 单字符回文长度 1，双字符看是否相同。
• ③ 按区间长度从小到大枚举——这是区间 DP 的核心。必须先算短的区间，才能算长的。
• ④ 两端字符相同，它们可以同时被选入回文子序列，所以长度 +2。
• ⑤ 两端不同，至少有一端不被选，取去掉左端或右端的较大值。

模拟：$S$ = “kazan”。

l\r	0(k)	1(a)	2(z)	3(a)	4(n)
0	1	1	1	3	3
1		1	1	3	3
2			1	1	1
3				1	1
4					1

逐行计算：

• dp[1][3]：S[1]=‘a’, S[3]=‘a’，两端相同 → dp[2][2]+2 = 1+2 = 3（回文子序列 “aza”）。
• dp[0][3]：S[0]=‘k’, S[3]=‘a’，不同 → max(dp[1][3], dp[0][2]) = max(3,1) = 3。
• dp[1][4]：S[1]=‘a’, S[4]=‘n’，不同 → max(dp[2][4], dp[1][3]) = max(1,3) = 3。
• dp[0][4]：S[0]=‘k’, S[4]=‘n’，不同 → max(dp[1][4], dp[0][3]) = max(3,3) = 3。

答案 = $dp[0][4] = 3$。最长回文子序列 “aza”（S[1], S[2], S[3]）。✓

参考文献

教材讲解 — 競技プログラミングの鉄則 第 4 章

• 4.5 B20 Edit Distance（编辑距离 解说）
• 4.6 B21 Longest Subpalindrome（回文子序列 解说）
• 4.9 B24 Many Boxes（LIS 贪心+二分 解说）

系统练习 — 競技プログラミングの鉄則

• A20 LCS（最长公共子序列）【例题】
• A24 LIS（最长递增子序列）【例题】
• B20 Edit Distance（编辑距离）【例题】
• B21 Longest Subpalindrome（最长回文子序列）【例题】
• B24 Many Boxes（LIS 贪心+二分）

实战练习 — 競プロ典型 90 問

• 060 Chimera（★5，先增后减 = 正反 LIS）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化