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

下面代码求从包含非负元素的数组中选择若干个互不相邻元素所能得到的最大和。横线处应填写 （　　）。

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

看到这题先想"最优子结构"和"重叠子问题"——这是动态规划的标志性特征。题目要求选互不相邻元素，意味着选第 i 个时，第 i-1 个必须放弃，因此状态转移只能来自 dp[i-1]（不选 a[i]）或 dp[i-2]+a[i]（选 a[i]）。这类题的通法是：定义 dp[i] 为前 i 个元素的最优解，然后写出"选/不选"的两种情况，再取 max。

选项 A 和 D 都忽略了"不选 a[i] 时也要考虑 dp[i-1] 的情况"，选项 B 则完全丢掉了"不选 a[i]"的分支。最阴险的陷阱是"相邻元素"的语义——dp[i-1] 已经包含了 a[i-1] 的可能性，若直接加 a[i] 就会违反互不相邻。边界条件 dp[1]=max(a[0],a[1]) 也常被误写成 a[0]+a[1]。

1. 考纲定位

本题考查《GESP 六级大纲》"动态规划"模块的核心考点。命题人放这道题是为了卡住考生对"状态转移方程"的直觉——六级考生往往能写出 dp 数组，但一到"选或不选"的分支就卡壳。

2. 解题思维

看到互不相邻的最大和问题，先想：选第 i 个元素时，第 i-1 个必须放弃，所以只能从 dp[i-2] 接上 a[i]；不选第 i 个，最优解就是 dp[i-1]。因此 dp[i] = max(dp[i-1], dp[i-2] + a[i])。

验证边界：dp[0]=a[0]，dp[1]=max(a[0],a[1])，递推从 i=2 开始，完全吻合。