GESP 六级 · GESP 202309 C++ 六级 第 13 题

青蛙每次能跳 1 或 2 步。下面是青蛙跳到第 $N$ 步台阶 C++ 实现代码。该段代码采用的算法是（ ）。

int jumpFrog(int N) {
    if (N <= 3)
        return N;
    return jumpFrog(N - 1) + jumpFrog(N - 2);
}

（洛谷注：本题答案存在争议）

这题代码看着像递归，但问的是‘算法’。别被递归写法带偏，先剥离代码看数学本质：它把大问题拆成两个小问题（N-1 和 N-2）然后合并，这就是动态规划里最经典的斐波那契递推模型。

最容易掉进‘递归就是递归算法’的坑。贪心算法是局部最优不回头，这题显然不是；分治算法强调‘分、治、合’且子问题通常独立，而这题子问题重叠严重（算 N-1 时会重复算 N-2），所以不是分治。命题人专门用递归写法迷惑人，其实考的是你对算法思想的理解，而不是语法。

【考点】递归与动态规划思想、斐波那契数列递推、算法定义辨析

【概念人话版】动态规划的核心就两点：一是问题有最优子结构（大问题的解包含小问题的解），二是子问题重叠（算 N-1 时又得算 N-2，不能只算一次）。递归只是实现动态规划的一种写法，真正的算法思想是‘把大问题拆成小问题，小问题算完再拼起来’。斐波那契数列就是最典型的例子：f(n)=f(n-1)+f(n-2)，n>2 时完全由前两项决定。

【命题人怎么挖坑】这道题代码只给了一个递归函数，没有记忆化数组，也没有迭代写法，很容易让人以为它在考‘递归算法’。但题目问的是‘该段代码采用的算法’，不是‘这段代码用了什么语法’。命题人故意用递归形式包装，就是想卡住那些只会背‘递归=递归算法’的考生。另外，贪心算法是局部最优不回头，分治算法强调子问题独立，这两者都和本题的递推结构不符，都是干扰项。

【拿到题先想什么→从哪入手】看到 jumpFrog(N-1)+jumpFrog(N-2) 立刻联想到斐波那契递推式。这一类题的通法是：识别递推关系，再判断是否适合用动态规划（加记忆化或迭代）优化。本题 N<=3 时直接返回 N，说明初始值 f(1)=1, f(2)=2, f(3)=3，之后按递推式计算。所以算法主线就是：把大问题拆成两个小问题，小问题算完再合并。

【一步步推演】当 N=4 时，jumpFrog(4)=jumpFrog(3)+jumpFrog(2)=3+2=5；N=5 时，jumpFrog(5)=jumpFrog(4)+jumpFrog(3)=5+3=8……这就是典型的动态规划递推过程。虽然代码里用了递归，但思想完全符合动态规划的定义。

【避坑】A 选项‘递推算法’表述不严谨，递推只是动态规划的一部分，不能单独作为算法名称；B 选项‘贪心算法’明显错误，因为青蛙不能只跳 2 步，必须考虑所有可能；D 选项‘分治算法’最阴险——代码虽在‘分’，却未体现‘治’和‘合’的独立性，反而把问题拆解成两个子问题后直接求和，正是动态规划的 2 个子问题状态转移。所以正确答案只能是 C。

【考频与趋势】动态规划在题库共考过 120 题，覆盖 9 个考试级别（2009-2026）；逐年分布：2009 年 1 题、2010 年 2 题、2019 年 2 题、2021 年 1 题、2022 年 1 题、2023 年 14 题、2024 年 24 题、2025 年 25 题、2026 年 30 题、null 年 20 题；分赛事：GESP 六级 38 题、GESP 七级 29 题、CSP 入门级 22 题、GESP 八级 18 题、CSP 提高级 6 题、GESP 五级 3 题、NOIP 普及组 初赛 2 题、GESP 四级 1 题、NOIP 提高组 初赛 1 题。从数据看，动态规划近年考频持续上升，2026 年达到 30 题，说明命题人越来越喜欢用这种递推模型考查学生对算法思想的把握。

【预测】基于给定数据与经验，未来 GESP 六级和 CSP 入门级仍会高频出现动态规划题目，且更倾向于用递归或记忆化搜索的形式包装，以区分单纯会写代码和真正理解算法思想的考生。暂无足够依据预测具体题型变化，但可预期难度会随考频增加而逐步提升。