GESP 七级 · GESP202609 C++ 七级 第 11 题

用动态规划求两个序列 s₁ 和 s₂ 的最长公共子序列长度，若 dp[i][j] 表示 s₁ 前 i 个元素与 s₂ 前 j 个元素的 LCS 长度。当 s₁[i−1] = s₂[j−1] 时，正确的状态转移是（　）。

LCS 经典 DP 题，核心是区分两种情形：当 s₁[i−1] = s₂[j−1] 时，两字符能同时纳入公共子序列，状态转移为 dp[i][j] = dp[i−1][j−1] + 1；当不相等时，只能舍弃一个字符，取 dp[i−1][j] 与 dp[i][j−1] 的最大值。本题只问相等情形，直接对应选项 A。

选项 B 是"不相等"时的转移，属于偷换条件；C、D 都只单向继承并强行 +1，忽略了 LCS 必须取最优子结构——当字符相等时，最优解必然来自左上角 dp[i−1][j−1]，而非仅继承上方或左方。考生易混淆"匹配"与"不匹配"两种分支，导致选错。

1. 考纲定位

本题考查《GESP 考试大纲》七级"动态规划"模块中的经典 LCS 状态转移。命题人放这道题，就是要卡住那些只背公式、不理解 DP 状态含义的考生——他们往往把"相等时 +1"当成无条件操作，却忘了 +1 的前提是必须从 dp[i−1][j−1] 继承，而非从 dp[i−1][j] 或 dp[i][j−1] 继承。

2. 解题思维

看到"最长公共子序列"先想到 DP 表 dp[i][j] 表示 s₁前 i 个与 s₂前 j 个的 LCS 长度。关键观察是：当 s₁[i−1] = s₂[j−1] 时，这两个字符必然同时出现在最优公共子序列中，因此 dp[i][j] 等于 dp[i−1][j−1] 再加 1。这是 LCS 的"匹配分支"。

若 s₁[i−1] ≠ s₂[j−1]，则最优解只能舍弃其中一个字符，取 max(dp[i−1][j], dp[i][j−1])，这是"不匹配分支"。

本题只问相等情形，直接套用匹配分支：dp[i][j] = dp[i−1][j−1] + 1，对应选项 A。