P4749 青蛙跳（入门）

解题思路

青蛙上台阶，一次可以跳 1 层，也可以跳 2 层，问上到第 n 层台阶有多少种跳法。

想一想青蛙最后一步：如果它在第 n-1 层，跳 1 层就到了第 n 层；如果它在第 n-2 层，跳 2 层也到了第 n 层。所以到达第 n 层的跳法数 = 到达第 n-1 层的跳法数 + 到达第 n-2 层的跳法数，即 f(n)=f(n-1)+f(n-2)。

再看最开头：第 1 层只有 1 种跳法（跳 1 层）；第 2 层有 2 种跳法（一次跳 2 层，或者分两次各跳 1 层）。这两个就是递归的出口。

用例子验证：f(3)=f(2)+f(1)=2+1=3，f(4)=3+2=5，f(5)=5+3=8，和样例一致。这就是著名的斐波那契数列。

边界情况：题目保证 1≤n≤20，n 最大是 20，f(20)=10946，int 完全装得下。递归深度最多 20 层，不会栈溢出。

注意：这道题和"递归版台阶问题"本质上是一样的思路，都是斐波那契数列。关键是把最后一步分成"跳1层"和"跳2层"两种情况来想：到第 n 层的所有跳法，要么最后一步跳 1 层，要么最后一步跳 2 层，两种情况互不重复，加起来就是答案。

参考代码

// 青蛙跳：一次跳1层或2层，递归求上n层台阶的跳法数
#include <iostream>

int jump(int n) {
    if (n == 1) return 1;                  // 1层台阶：1种跳法
    if (n == 2) return 2;                  // 2层台阶：1+1 或 2
    return jump(n - 1) + jump(n - 2);      // 最后一次跳1层或2层
}

int main() {
    int n;
    std::cin >> n;
    std::cout << jump(n) << "\n";
    return 0;
}

复杂度分析

直接递归的时间复杂度是 O(2^n)，因为每个 f(k) 都会分成两个子问题。但 n 最大只有 20，2^20 约 100 万次调用，仍然能在 1 秒内完成。空间上递归深度最大是 n 层，占用 O(n) 的栈空间。如果题目把 n 改成很大的数（比如 10^6），就需要用递推或记忆化把复杂度优化到 O(n)，但本题数据范围小，简单递归即可。