GESP 六级 · GESP 202406 C++ 六级 第 12 题

青蛙每次能跳 $1$ 或 $2$ 步，下面代码计算青蛙跳到第 $n$ 步台阶有多少种不同跳法。则下列说法，错误的是（ ）。

int jump_recur(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return jump_recur(n - 1) + jump_recur(n - 2);
}

int jump_dp(int n) {
    vector<int> dp(n + 1); // 创建一个动态规划数组，用于保存已计算的值
    // 初始化前两个数
    dp[1] = 1;
    dp[2] = 2;
    // 从第三个数开始计算斐波那契数列
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

斐波那契数列：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递归｜动态规划｜时间复杂度

先看函数类型：jump_recur 不断调用自身，是典型的递归实现；jump_dp 用数组存中间结果，是动态规划。再看效率：递归没有记忆化，计算 jump_recur(n) 时，jump_recur(n-1) 和 jump_recur(n-2) 会各算一遍，子问题重复计算呈指数级增长，时间复杂度 O(2^n)，n 稍大就会卡死。动态规划每个状态只算一次，O(n)。选项 A、B、C 都符合事实，D 说"执行效率高"明显错了。

命题人最阴险的陷阱在 D 的"代码量小，执行效率高"。代码行数确实少，但"执行效率高"是算法层面的评价，和代码量无关。学生容易混淆"代码简洁"和"运行快"，把代码行数当效率指标。命题人故意用"代码量小"这个事实性描述，诱使只关注语法而忽略时间复杂度的考生掉坑。

命题人视角：把 jump_recur 改成"带记忆化的递归"（加个 dp 数组），代码量就变大了，但效率提升，这时 D 就变成对的。这类题的本质是考"递归与动态规划的性能差异"，刷到类似题先问"命题人想考我什么"，别被代码行数带偏。