GESP 七级 · GESP 202606 C++ 七级 第 6 题

已知 $f[0]=0$，$f[1]=2$，并且对 $i\ge 2$ 有 $f[i]=\max(f[i-1], f[i-2]+a[i])$。若 $a[1..5]=\{2,7,9,3,1\}$，则 $f[5]$ 的值为（ ）。

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划｜递推关系｜最优子结构

1. 考纲定位 GESP 七级"递推与动态规划"模块。命题人用这题卡住的是：明明只给了两行递推式，考生却硬要去凑"前缀和"、"单调性"等高级概念，结果算到一半就懵了。

2. 解题思维 看到 $f[i]$ 只依赖 $f[i-1]$ 和 $f[i-2]$，立刻锁定递推结构。从 $i=2$ 起逐项推进：$f[2]=\max(2,0+7)=7$；$f[3]=\max(7,2+9)=11$；$f[4]=\max(11,7+3)=11$；$f[5]=\max(11,11+1)=12$。核心就三点：初始值照抄、每次取两候选的最大值、前向计算无回溯。

3. 陷阱拆解 A 项 10 是把 $f[5]$ 算成 $f[4]+a[5]=11+1=12$ 后误以为 $f[4]$ 应是 10，这源于把 $f[i-1]$ 当成"前一项总和"；B 项 11 是只取了 $f[i-1]$ 一路递推，忽略了 $f[i-2]+a[i]$ 可能更大；D 项 13 则像把 $a[5]$ 误当成 $12$ 或多加了某个项。最阴险的是 $f[4]$ 本该是 $11$ 却有人算成 $10$——因为 $f[2]+a[4]=7+3=10$，若只盯着这一项就掉进局部最优陷阱。

4. 反命题思维 若把 $\max$ 换成 $\min$，答案会立刻变成 $f[5]=\min(11,12)=11$；若 $a[5]$ 改为 $5$，则 $f[5]=\max(11,11+5)=16$。刷到同类题先问：递推式到底是选大的还是选小的？有没有可能 $a[i]$ 为负导致 $f[i-2]+a[i]$ 反而更小？