P4746 递归版台阶问题（入门）

解题思路

小鹿上楼梯，一步可以跨 1 个台阶，也可以跨 2 个台阶，问上到第 n 个台阶一共有多少种走法。

我们来想一想最后一步：小鹿要上到第 n 个台阶，最后一步要么从第 n-1 个台阶跨 1 格上来，要么从第 n-2 个台阶跨 2 格上来。所以走到第 n 个台阶的走法数，等于走到第 n-1 个台阶的走法数，加上走到第 n-2 个台阶的走法数。即 f(n)=f(n-1)+f(n-2)。

再看开头：只有 1 个台阶时，只能直接跨 1 格，所以 f(1)=1；有 2 个台阶时，可以一次跨 2 格，也可以分两次各跨 1 格，所以 f(2)=2。这两个就是递归的出口。

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

边界情况：题目保证 1<n<20，n 最大是 19。f(19)=4181，没有超过 int 范围。递归深度最多 19 层，非常安全。注意如果把 n 范围扩大很多，直接递归会重复计算，但本题数据小，直接递归足够。

参考代码

// 递归版台阶问题：一步1格或2格，求上到第n个台阶的走法数
#include <iostream>

int step(int n) {
    if (n == 1) return 1;                  // 只有1个台阶：1种走法
    if (n == 2) return 2;                  // 2个台阶：1+1 或 2
    return step(n - 1) + step(n - 2);      // 最后一步跨1格或跨2格
}

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

复杂度分析

直接递归的时间复杂度是 O(2^n)，因为每个 f(k) 都要分成两个子问题。但 n 最大只有 19，2^19 约 52 万次调用，仍然很快。空间上递归深度最大是 n 层，是 O(n) 的栈空间。如果以后遇到很大的 n，可以改用递推或记忆化，把复杂度优化到 O(n)，但本题数据范围小，简单递归就足够了。