【模板】最长公共子序列

形式化题目

给定两个大写字母串 $X=x_1x_2\cdots x_n$ 与 $Y=y_1y_2\cdots y_m$ 。求最大的 $k$ ，使得存在两组严格递增的下标

i_1<i_2<\cdots<i_k,\qquad j_1<j_2<\cdots<j_k

满足对每个 $t$ 都有 $x_{i_t}=y_{j_t}$ 。这个 $k$ 就是最长公共子序列（LCS）的长度；若两串没有公共字符，答案为 $0$ 。

暴力解法

思路

最直白的做法就是把 $X$ 的所有子序列都造出来，逐个检查它是否也是 $Y$ 的子序列。

"造出所有子序列"天然是一棵选择树： $X$ 的每个字符只有选和不选两种决定， $n$ 个字符一共产生 $2^n$ 条完整的 01 选择序列。于是用全局数组 choose[] 记录每层的选择，dfs(dep) 只负责决定第 dep 个字符选不选，并把选中的字符依次拼进 candidate：

dep > n 说明一条完整的 01 序列生成完毕，此时 candidate 就是一个 $X$ 的子序列；
在叶子节点做两件事：检查 candidate 是否是 $Y$ 的子序列，是的话用它的大小更新答案。

"是 $Y$ 的子序列"用一个指针在 $Y$ 上顺序扫描即可：pos 指向 candidate 中等待匹配的字符，遇到相同的就前进一步，扫完 Y 时 pos 走到末尾就说明匹配成功。

选择序列先生成、后检查，逻辑最短，也最容易确认它没有漏掉任何方案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-19 18:07
 * update_at: 2026-09-19 18:07
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举 X 的所有子序列。
// 每一层决定 X 的第 dep 个字符选或不选，选出来的字符按原顺序拼成 candidate；
// 到了叶子节点再检查 candidate 是否是 Y 的子序列，是就更新答案。
// 只有 n <= 20 左右才跑得动，只用来对拍和理解题意。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

string x, y;

int n;              // 序列 X 的长度，递归层数就是它
int choose[MAXN];   // choose[i] 表示 X 的第 i 个字符选(1)还是不选(0)
string candidate;   // 由 X 中所有被选的字符按原顺序拼成的子序列
int ans;            // 目前找到的最长公共子序列长度

// 判断 s 是否是 y 的子序列：在 y 上顺序扫描，能依次匹配完 s 就算成功。
bool is_subsequence(const string &s) {
    int pos = 0;
    for (int i = 0; i < (int)y.size() && pos < (int)s.size(); i++) {
        if (y[i] == s[pos]) pos++;
    }
    return pos == (int)s.size();
}

void dfs(int dep) {
    if (dep > n) {
        // 完整的选择序列已经生成，检查候选子序列并统计答案
        if (is_subsequence(candidate)) {
            if (ans < (int)candidate.size()) ans = candidate.size();
        }
        return;
    }

    // 这一层选择 X 的第 dep 个字符：0 不选，1 选
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        if (i == 1) candidate.push_back(x[dep - 1]);
        dfs(dep + 1);
        if (i == 1) candidate.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x >> y;
    n = x.size();

    dfs(1);
    cout << ans << "\n";

    return 0;
}

复杂度

时间： $2^n$ 条选择序列，每条在叶子节点花 $O(n+m)$ 检查，总 $O(2^n(n+m))$ 。
空间：candidate 最长 $n$ ，递归栈深 $n$ ， $O(n)$ 。

瓶颈

瓶颈不在检查，而在枚举量 $2^n$ ： $n=200$ 时子序列个数是一个 61 位数。更本质的问题是重复——不同的 01 选择序列经常产生同一个串（ $X$ 里有重复字符），或者产生"已经不可能更优"的串，暴力把它们全部重新算了一遍。

换个角度想：判断一个候选串够不够长，其实只和"用掉了 $X$ 的哪个前缀、 $Y$ 的哪个前缀"有关。如果我们直接按前缀推进，就只需要 $n\times m$ 个状态。

正解

思路

一句话本质：把"枚举子序列"换成"同步推进两个前缀"——公共子序列的长度只由两个前缀决定，与具体选了哪些字符无关，于是指数级的方案被压缩成 $n\times m$ 个状态。

设

$$f(i,j)=\text{$ X$ 的前 $i$ 个字符与 $Y$ 的前 $j$ 个字符的最长公共子序列长度}

边界是 $f(i,0)=f(0,j)=0$ （其中一边为空串时，公共子序列只能是空串）。下面分两种情况推出转移。

问题？ 如果 $x_i=y_j$ ，这对字符要不要一起用？

要。把这两个相同的字符接到 $f(i-1,j-1)$ 的公共子序列后面，就得到 $X$ 前 $i$ 个字符与 $Y$ 前 $j$ 个字符的一个公共子序列，长度是 $f(i-1,j-1)+1$ ；而任何最长公共子序列去掉最后一个字符后，仍是更小前缀对的公共子序列，长度不超过 $f(i-1,j-1)$ 。所以

f(i,j)=f(i-1,j-1)+1,\qquad x_i=y_j

问题？ 如果 $x_i\ne y_j$ ，该怎么办？

它们不可能同时成为最长公共子序列的最后一个字符（那样就必须相等），所以至少有一个要被丢掉：要么 $x_i$ 用不上，退回 $f(i-1,j)$ ；要么 $y_j$ 用不上，退回 $f(i,j-1)$ 。取两者较优：

f(i,j)=\max\bigl(f(i-1,j),\ f(i,j-1)\bigr),\qquad x_i\ne y_j

问题？ 这样算为什么不会漏掉真正的答案？

因为每一步都只做"用掉 $x_i$ 和 $y_j$ "或"至少丢掉其中一个"这两种选择，任何一条合法匹配路径都会落在其中一种情况里，取 $\max$ 就是最优。

下面用样例 $X=\texttt{ABCBDAB}$ 、 $Y=\texttt{BDCABA}$ 手工填一部分表，看两种转移怎么起作用（ $f(0,\cdot)=f(\cdot,0)=0$ ）：

$f(i,j)$	B	D	C	A	B	A
$i{=}0$	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4

看两个典型格子。 $f(2,2)$ （ $X$ 的 AB 对 Y 的 BD）： $b\ne d$ ，取 $\max(f(1,2),f(2,1))=\max(0,1)=1$ ，即公共子序列 B。 $f(7,6)$ （整串）： $x_7=y_6=\texttt{A}$ ，取 $f(6,5)+1=3+1=4$ ，对应 BCBA（也可取 BDAB）。

问题？ 表有 $(n+1)(m+1)$ 个格子，会不会太多？

不会。题面数据只有 $n,m\le 1000$ ，表最多 $10^6$ 个 int，四个字节一个也就 4 MB，直接开 int dp[1005][1005] 存整张表最省心：不用推敲行号怎么翻转，出错时也能直接打印任意一个 $f(i,j)$ 手工对照公式。

如果数据范围再大一个数量级，才需要优化空间：转移只用到"上一行同列"“上一行左一列”"本行左一列"三种来源，可以只保留两行滚动覆盖，空间从 $O(nm)$ 降到 $O(m)$ 。本题用不上这种写法，但它值得知道。

用 std::string 存两个串最贴合题意：cin >> a >> b 一次读完整行，a.size() 就是 $n$ ，a[i-1] 正好是公式里的 $x_i$ ，不必自己维护长度，两串长度不同也不需要额外处理。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-19 18:07
 * update_at: 2026-09-19 18:07
 */
// main.cpp：最长公共子序列（LCS）长度，O(nm) 的朴素 DP，直接用 string 当作字符序列。
#include <bits/stdc++.h>
using namespace std;

string a, b;  // 读入的两个序列，下标从 0 开始，长度分别是 a.size()、b.size()
int dp[1005][1005];  // dp[i][j] = LCS(a 的前 i 个字符, b 的前 j 个字符)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;

    int n = a.size();  // 序列 X 的长度
    int m = b.size();  // 序列 Y 的长度

    // 第 0 行、第 0 列表示其中一个串为空，公共子序列只能是空串
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                // 两个字符相同，可以直接把它们接在 LCS(a[0..i-2], b[0..j-2]) 后面
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 否则 X 的第 i 个字符和 Y 的第 j 个字符不可能同时出现在 LCS 的末尾
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // dp[n][m] 就是两个完整串的 LCS 长度
    cout << dp[n][m] << "\n";

    return 0;
}

复杂度

时间： $n\times m$ 个状态，每个 $O(1)$ 转移，总 $O(nm)$ 。
空间：二维数组 dp[1005][1005]（约 4 MB）加两个串， $O(nm+n+m)$ 。

总结

核心模型：前缀 DP。 $f(i,j)$ 表示两个前缀的 LCS 长度，答案 $f(n,m)$ ；关键是意识到"长度只与两个前缀有关"，从而把 $2^n$ 条选择序列压缩成 $n\times m$ 个状态。
两种转移： $x_i=y_j$ 时 $f(i,j)=f(i-1,j-1)+1$ （这对字符值得一起用）； $x_i\ne y_j$ 时 $f(i,j)=\max(f(i-1,j),f(i,j-1))$ （必有一个要丢掉）。
实现技巧：用 int dp[1005][1005] 直接存整张表，dp[i][j] 就是 $f(i,j)$ ，不必推导行的滚动映射，出问题时能直接打印表格对照公式；数据范围更大时再把其中一维压成两行。
暴力与正解的关系： $O(2^n)$ 枚举子序列直观但重复严重，DP 正是为消除这种重复而出现的——"每个前缀对只算一次"是这一类题的通用思路，也是所有序列型 DP 的起点。