GESP 八级 · GESP 202412 C++ 八级 第 11 题

下面最长公共子序列程序中，横线处应该填入的是（ ）。

#define MAX(A, B) ((A) > (B)) ? (A) : (B)
#define MIN(A, B) ((A) < (B)) ? (A) : (B)
int dp[MAX_L + 1][MAX_L + 1];
int LCS(char str1[], char str2[]) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for (int i = 0; i < len1; i++)
        for(int j = 0; j < len2; j++)
            if (str1[i] == str2[j])
                dp[i + 1][j + 1] = dp[i][j] + 1;
            else
                _______;  // 在此处填入选项
    return dp[len1][len2];
}

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】动态规划｜字符比较｜递推关系

🎯 考纲定位 GESP 八级算法与程序设计第 5 章动态规划，第 2 节经典问题。命题人卡住的是你"背了 LCS 套路但没真正理解状态转移"——绝大多数考生会机械记忆"相等时+1，不等时取max"，却在实现时把取max写成相加，或在不相等时错误地+1。

🧠 解题思维 看到题先想动态规划的经典套路：dp[i][j] 表示 str1 前 i 个与 str2 前 j 个的 LCS 长度。当 str1[i] == str2[j] 时，直接继承 dp[i][j] 并 +1；当不相等时，当前状态只能从"去掉 str1[i]"或"去掉 str2[j]"两个子问题中选最优解，即取 max(dp[i][j+1], dp[i+1][j])。

🪤 陷阱拆解 逐个拆选项：A 把两个子状态直接相加，"ab"和"ac"时 dp[1][2]=1、dp[2][1]=1 却算出 2，明显超了；B 用 MIN 取较小值，逻辑反了；D 在不相等时还 +1，相当于强行造匹配。C 是标准取 max 操作，命题人最爱用"绝对化表述"（如 +1）和"偷换概念"（把取 max 写成相加）来挖坑。

🔄 反命题思维 反命题视角：如果把 else 条件改成 str1[i] != str2[j]，答案仍是 MAX 但下标要调整为 dp[i][j+1] 和 dp[i+1][j]；若改成 dp[i][j] = min(...)，题目就会变成求最短公共超序列（LCS 的逆向）。刷到类似题先问"命题人想考我什么"，别死记硬背。