CSP-S 提高级 · CSP 2023 提高级第一轮 第 7 题

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 $X={x_1,x_2,x_3,\cdots,x_m}$ 和 $Y={y_1,y_2,y_3,\cdots,y_n}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z={z_1,z_2,z_3,\cdots,z_k}$, 使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里是最大的。 （注：序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

这题考最长公共子序列（LCS）求长度。别急着肉眼凑，先把两个串对齐，从左上角开始模拟动态规划填表，遇到相同字符就加 1，不同就取左右上边的最大值，最后右下角那个数就是答案。

最容易掉进两个坑：一是把 LCS 当成连续子串去搜，结果漏掉很多能跳着选的字符，比如把 A 和后面的 A 当成不能连用；二是看到 C 在 X 里只出现一次就以为只能选一次，其实 C 在 Y 里也有，只要顺序对就能用。还有就是填表时粗心，把 dp[i][j] 算成了 dp[i-1][j-1]+1，其实只有当 X[i]==Y[j] 时才加 1，否则要取 max(dp[i-1][j], dp[i][j-1])。

这道题考查什么？

这是典型的字符串算法题，核心就是求两个序列的最长公共子序列（LCS）长度。题目给的是两个字符串：X = ABCAAAABA 和 Y = ABABCBABA，让你选一个数。

概念：什么是子序列？

很多人容易把“子序列”和“子串”搞混。子串必须连续，比如 ABC 是 ABCDE 的子串；但子序列可以不连续，只要相对顺序不变就行。像 ACE 也是 ABCDE 的子序列，因为 A、C、E 在原串里顺序没变，只是中间跳过了 B、D。LCS 就是找两个串里最长的、都作为子序列出现的那个。

命题人怎么挖坑？

这题是 CSP 提高级 2023 的单选题，命题人特意给了两个长度都为 9 的串，而且里面全是 A、B、C 这种常见字母，很容易让人用肉眼去“凑”。但肉眼凑有两个大坑： 1. 容易误以为 LCS 要连续，把 A 和后面的 A 当成不能连用； 2. 容易忽略 C 在两个串里都只出现一次，以为只能选一次。 其实只要顺序对，跳着选完全合法。

思考心法：拿到题先想什么？

别直接数，先画个二维表格。设 dp[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的 LCS 长度。递推规则很简单：

• 如果 X[i] == Y[j]，那这个字符肯定能接在之前的最优解后面，所以 dp[i][j] = dp[i-1][j-1] + 1；
• 如果 X[i] != Y[j]，那这个字符要么不用，要么用在另一边，所以 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

一步步推（手算版）：

X: A B C A A A A B A Y: A B A B C B A B A

我们只关心最终结果，但可以模拟几个关键步骤：

• 前两个字符都是 A、B，dp[2][2] = 2（AB）；
• 第三个字符 C 在 Y 里还没出现，dp[3][3] 还是 2；
• 当 Y 的第四个字符 B 出现时，X 里也有 B，dp[4][4] = dp[3][3] + 1 = 3（ABC 或 ABB）；
• 继续往后，C 在 Y 的第五个位置出现，X 里也有 C，dp[5][5] = dp[4][4] + 1 = 4；
• 后面全是 A、B，每次遇到相同的就 +1，不同的就取 max。

填完整个表格，右下角 dp[9][9] 的值就是 6。其中一个长度为 6 的公共子序列是 ABCBAA（或者 ABABBA 等等），你可以自己验证一下：这两个串里确实能按顺序挑出这 6 个字符，而且找不到 7 个了。

避坑提醒：

千万别用肉眼去“找最长”，很容易漏掉。比如有人可能只看到 A、B、C、A、B、A 这六个，却忘了后面还能再拼一个 B，或者误以为 C 只能用一次。记住：LCS 不要求连续，只要顺序对，跳着选完全合法。

考频与趋势：

从题库数据看，LCS 属于“简单动态规划”大类，历年共考过 94 题，覆盖 8 个考试级别。其中 CSP 提高级只考了 4 题，但 2023 年这一年就考了 15 题，说明这题在提高级里属于高频考点。字符串算法整体考过 7 题，2023 年也考了 1 题，2025 年考了 3 题，呈现逐年上升的趋势。

预测：

既然 2025 年字符串算法考了 3 题，且 LCS 在提高级 2023 年已经出现，未来几年（比如 2026 年）很可能还会继续考类似的 LCS 或相关变体，比如求 LCS 的长度、或者求 LCS 的具体序列、甚至扩展到三个串的最长公共子序列。暂无足够依据预测具体年份，但可以肯定的是，这题在提高级里会持续出现。