GESP 六级 · GESP 202606 C++ 六级 第 14 题

给定一个整数数组 a，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(vector<int>& a) 返回能够得到的最大总和，则横线处应填写（ ）。

int choose(vector<int>& a) {
    if (a.empty()) return 0;
    int n = a.size();
    if (n == 1) return a[0];
    vector<int> dp(n, 0);
    dp[0] = a[0];
    dp[1] = max(a[0], a[1]);
    for (int i = 2; i < n; ++i) {
        dp[i] = __________________________;
    }
    return dp[n - 1];
}

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

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

【考点】动态规划｜状态转移方程｜互斥选择

1. 🎯 考纲定位 GESP 六级"动态规划与贪心"模块核心题型。命题人卡住的是考生对"决策互斥"的理解——以为选当前就能直接加，却忘了它和 i-1 冲突，必须回溯到 i-2。这是六级从基础 DP 进阶到"依赖状态"阶段的分水岭题。

2. 🧠 解题思维 看到"不相邻"限制，立刻想到：选第 i 个元素时，它和 i-1 冲突，必须用 i-2 的最优解；不选 i 则继承 i-1 的最优解。因此状态转移方程必然是 dp[i] = max(dp[i-1], dp[i-2] + a[i])。这是处理"互斥选择"类问题的通用套路——任何只能二选一且互斥的 DP，状态都会依赖两个前驱。

3. 🪤 陷阱拆解 陷阱藏在选项 A 和 C。A 写成 dp[i-1] + a[i] 看似合理，实则允许选了 i-1 又选 i，违反不相邻规则；C 的 max(dp[i-2], a[i]) 直接丢弃了 i-1 的累积结果，无法处理连续的大值。命题人故意用"dp[i-1]"这个绝对化表述诱导只关注当前决策的考生掉坑——以为前面最优解一定包含 i-1，却没考虑 i-1 本身被选时 i 就不能选。

4. 🔄 反命题思维 若把"不相邻"改成"最多选 k 个"，答案会变为三维 DP dp[i][k]；若允许相邻，直接全选即可。这类题本质是测试你是否真正理解"状态依赖"，而非机械套用结论。