形式化题目

给定两个由大写字母组成的字符串 $X$、$Y$，长度均不超过 $1000$。 一个串 $Z$ 是串 $S$ 的子序列，当且仅当 $Z$ 的每个字符在 $S$ 中按顺序出现（可删去 $S$ 中任意字符）。 求 $X$、$Y$ 的公共子序列中长度最大的值。

正解

思路

设 $dp[i][j]$ 表示前缀 $X[0..i-1]$ 与前缀 $Y[0..j-1]$ 的最长公共子序列长度。

考虑最后一对字符 $X[i-1]$ 与 $Y[j-1]$：

• 若 $X[i-1] = Y[j-1]$，这两个字符可以同时作为某个最长公共子序列的末尾字符， 因此
  $$dp[i][j] = dp[i-1][j-1] + 1。$$
• 若 $X[i-1] \neq Y[j-1]$，则最优解不会同时使用这两个字符， 于是去掉其中一个得到较短前缀的最优解，取两者较大值：
  $$dp[i][j] = \max(dp[i-1][j],\; dp[i][j-1])。$$

边界为 $dp[0][j] = dp[i][0] = 0$，即任一前缀与空串的 LCS 长度为 $0$。

样例 DP 表

以 $X = \text{ABCBDAB}$、$Y = \text{BDCABA}$ 为例，右下角即为答案：

表中加粗的 $4$ 位于右下角，与样例输出一致。

空间优化

递推式只依赖上一行 $prev$ 和当前行左侧已算出的值 $cur[j-1]$， 因此只需保存两行：

一轮结束后交换 $prev$ 与 $cur$。 注意 $j$ 必须从小到大遍历，因为 $cur[j]$ 会用到本行左侧的 $cur[j-1]$。

代码

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#!/usr/bin/env python3
# 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-01-14 22:00
# update_at: 2026-10-04 10:41

import sys


def solve() -> None:
    """最长公共子序列：滚动数组 DP。"""
    data = iter(sys.stdin.buffer.read().split())
    x, y = next(data), next(data)  # 两行序列，按 next() 顺序消费（字符数据，不转 int）
    n, m = len(x), len(y)

    prev = [0] * (m + 1)  # 上一行
    cur = [0] * (m + 1)   # 当前行

    for i in range(1, n + 1):
        xi = x[i - 1]
        for j in range(1, m + 1):
            if xi == y[j - 1]:
                cur[j] = prev[j - 1] + 1           # 匹配，继承左上 +1
            else:
                cur[j] = max(prev[j], cur[j - 1])  # 不匹配，取上方或左方较大者
        prev, cur = cur, prev  # 滚动：当前行变上一行，旧上一行复用为草稿

    print(prev[m])


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(nm)$，$n$、$m$ 分别为两串长度，均不超过 $1000$。
• 空间复杂度：$O(m)$，仅保留两行长度各为 $m+1$ 的整型数组。

总结

最长公共子序列是典型的二维动态规划模型。状态定义以两个前缀为维度，按末字符是否相等分类转移；再利用滚动数组把空间压到一维。实现时注意 $j$ 必须从小到大遍历，因为当前行依赖左侧同行的前一个值。