GESP 七级 · GESP 202512 C++ 七级 第 2 题

已知三个序列：s1 = {3, 1, 8, 2, 5, 6, 7, 4}，s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}，s3 = {1, 8, 3, 5, 7, 6, 2, 4}。以下哪个序列是它们的最长公共子序列（ ）。

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划｜最长公共子序列｜三维DP

先找三序列共同元素：s1含1,8,5,6；s2含1,8,6,5；s3含1,8,5,6。发现{1,8,5,6}在三个串中均按序出现。标准LCS是二维DP，三维LCS只需将状态表扩展为dp[i][j][k]，转移方程变为dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])，若三字符相等则+1。

选项B错在7不在s2中；选项C少了s3中5；选项D中7同样不在s2。命题人常设陷阱：把"子序列"偷换成"子串"（要求连续），或故意放一个在两个序列中都有但第三个没有的元素（如7）。若只背"最长公共"四个字，会忽略"子序列"的"顺序"约束，容易选错。

命题人想考的是DP思维迁移能力：从二维LCS到三维LCS，本质是状态扩展。刷到类似题先问：几个序列？元素是否重复？是否要求连续？若只套二维公式，遇到三维必栽。