GESP 七级 · GESP 202312 C++ 七级 第 8 题

下面代码段可以求两个字符串 $s1$ 和 $s2$ 的最长公共子串（LCS），下列相关描述不正确的是（ ）。

while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n1][n2] << endl;
}

这题考动态规划的空间复杂度分析。拿到代码先看状态转移方程，判断当前状态依赖哪些上一轮的数据，就能直接看出能不能压缩维度，别被二维数组的表象迷惑了。

很多考生看到二维 DP 就默认空间复杂度是 O(n^2)，认为已经是最优解了。其实只要状态只依赖上一行，就能用滚动数组优化到 O(n)。命题人专门挖这个坑，就是看学生是否真的理解状态转移的本质，而不是死记硬背结论。

这题考什么

这道题考查动态规划（DP）算法中空间复杂度的分析与优化能力，核心在于判断二维状态能否压缩为一维。

考点与概念

本题涉及的知识点是最长公共子串（LCS）的动态规划解法。LCS 问题要求找出两个字符串中最长的、连续出现的公共子串。解决这类问题的标准方法是构建一个二维数组 dp[i][j]，表示以 s1 第 i 个字符结尾和以 s2 第 j 个字符结尾的最长公共子串长度。

状态转移方程非常直观：

• 如果 s1[i-1] == s2[j-1]，说明当前字符匹配，长度在之前匹配的基础上加 1，即 dp[i][j] = dp[i-1][j-1] + 1；
• 如果不匹配，则当前位置的最长公共子串长度只能继承左边或上边的结果，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

命题视角：为什么考这个？

命题人设计这道题，目的非常明确：区分“会写代码”和“懂算法本质”的学生。在 GESP 七级这个级别，学生通常已经见过二维 DP 的模板，很容易机械地认为“用了二维数组，空间就是 O(n^2)，没法更小了”。但命题人特意把正确答案设为 C（声称空间已经最优），就是要戳破这个迷思。这反映了出题人的意图：考察学生对状态依赖关系的理解，而不是死记硬背复杂度公式。只有真正理解了状态转移方程中每一项的来源，才能发现其中隐含的优化空间。

思考心法：拿到题怎么想？

面对这类题，我的建议是：先看状态转移方程，再问自己“这一项到底需要谁？”

1. 拆解方程：把 dp[i][j] 的表达式拆开看。如果是 dp[i-1][j-1]，说明计算第 i 行第 j 列时，只需要知道第 i-1 行第 j-1 列的值。 2. 观察依赖：继续看另外两项 dp[i-1][j] 和 dp[i][j-1]。你会发现，无论哪种情况，计算当前行的所有元素时，只用到上一行（i-1）的数据。当前的 i 行数据一旦算完，就完全不需要再回头去查 i-2 行甚至更早的行。 3. 推导结论：既然只依赖上一行，那能不能把二维数组压扁成一维？当然可以！我们只需要两个一维数组（或者一个一维数组加一个临时变量），交替更新，就能模拟出二维的效果。这样空间复杂度就从 O(n^2) 降到了 O(n)。

逐空/逐问推演：代码里的细节

让我们回到题目给出的代码，逐行验证一下思路：

while (cin >> s1 >> s2) {
    memset(dp, 0, sizeof(dp));  // 初始化二维数组
    int n1 = strlen(s1), n2 = strlen(s2);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;  // 匹配：依赖左上角
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不匹配：依赖上方或左方
    cout << dp[n1][n2] << endl;
}

这里用了 memset 把整个二维数组清零，确实占用了 O(n^2) 的空间。循环嵌套两层，时间复杂度显然是 O(n1 * n2)，即 O(n^2)。选项 A 和 B 的描述完全正确。

关键是选项 C：“空间复杂度已经最优”。根据刚才的推演，这个说法是错的。因为状态转移只依赖上一行，我们完全可以用滚动数组优化。比如用 prev[j] 存上一行的值，curr[j] 存当前行的值，每算完一行就交换指针。这样空间直接降到 O(n2)，也就是 O(n)。所以 C 是命题人设的坑。

选项 D：“采用了动态规划求解”。这也没问题，代码里明确体现了 DP 的状态定义和转移，属于标准的 DP 实现。

避坑指南：学生最容易错在哪？

这道题最大的陷阱就是对二维数组的惯性思维。很多学生看到 dp[i][j] 就下意识地认为空间必须是 O(n^2)，觉得“二维就是二维，一维存不下”。其实只要状态转移不依赖多行，一维数组绝对够用。

另一个易错点是混淆“子串”和“子序列”。虽然这道题考的是子串（连续），但即使是最长公共子序列（不要求连续），其状态转移方程也是类似的（只是匹配时加 1，不匹配时取 max），同样可以用滚动数组优化到 O(n)。所以命题人故意用“已经最优”这种绝对化的表述，就是想看看学生是否真的理解了状态压缩的通用原理，而不是只针对这道题的死记硬背。

考频与趋势

从题库数据来看，动态规划是 GESP 七级的重头戏，共考过 29 题，其中 2023 年考了 14 题，2024 年 24 题，2025 年 25 题，2026 年更是达到了 30 题，呈现逐年上升的趋势。这说明 DP 在七级中的比重越来越大，学生必须熟练掌握。

在空间复杂度分析这个细分点上，题库共考过 39 题，且全部集中在 2026 年（11 题）和 null 年（28 题）。虽然目前只有 2026 年的数据，但考虑到 DP 整体的高频，这类考察状态压缩的题目在未来几年大概率会持续出现，尤其是在七级和六级中。

预测

基于 DP 在七级的高频趋势以及空间优化题目的稀缺性（目前仅 2026 年有少量记录），我预测在未来的 GESP 七级考试中，关于动态规划空间优化的题目仍将是高频考点。命题人可能会继续用类似的“绝对化表述”来设置陷阱，或者结合更复杂的场景（如三维 DP、带权 DP）来考察学生对状态依赖的洞察力。建议考生在复习时，不仅要会写二维 DP，更要刻意练习用滚动数组优化，把“状态只依赖上一行/前一列”这个特征刻在脑子里，这样才能在考场上一眼识破这类坑。