P4757 递归版台阶问题升级（入门）

解题思路

小鹿上楼梯，每一步可以迈 1 个台阶、2 个台阶或者 3 个台阶，我们要算出走到第 n 个台阶一共有多少种不同的走法。

先想最小的台阶数：

• 只有 1 个台阶：只能迈 1 步上去，1 种走法；
• 有 2 个台阶：可以 1+1 分两步走，也可以一步直接迈 2 个台阶，共 2 种走法；
• 有 3 个台阶：可以 1+1+1、1+2、2+1，或者一步迈 3 个台阶，共 4 种走法。

现在想第 n 个台阶：小鹿到第 n 个台阶的"最后一步"，要么是从第 n-1 个台阶迈 1 级上来，要么是从第 n-2 个台阶迈 2 级上来，要么是从第 n-3 个台阶迈 3 级上来。所以，到第 n 个台阶的走法数，等于到第 n-1、n-2、n-3 个台阶走法数之和：

f(n) = f(n-1) + f(n-2) + f(n-3)

这就把大问题拆成了三个小问题，非常符合递归的思路。比如 f(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7，和样例一致。

递归函数要有出口：n 等于 1、2、3 时直接返回对应的 1、2、4，其他情况就调用自己。可以把这条递推关系想象成"倒着数台阶"：每次站到第 n 级，只需要记住前面三级各有多少种走法，把它们加起来就行。题目保证 1 < n < 20，规模很小，直接递归完全够用。

参考代码

// 递归版台阶问题升级：一步可以上1、2、3个台阶，求到第n阶的走法数
#include <iostream>
using namespace std;

// 递归求到第n阶的走法数：最后一步分别可以上1、2、3阶，三类情况相加
int f(int n) {
    if (n == 1) return 1;   // 1个台阶只有1种走法
    if (n == 2) return 2;   // 2个台阶：1+1或直接上2
    if (n == 3) return 4;   // 3个台阶：1+1+1、1+2、2+1、3
    return f(n - 1) + f(n - 2) + f(n - 3);
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}

复杂度分析

f(n) 会递归调用 f(n-1)、f(n-2)、f(n-3)，调用次数大约和走法数 f(n) 同数量级。n < 20，f(19) 大约只有 6 万多，所以程序跑得非常快，时间复杂度大约 O(1.8^n)。递归深度是 n 层，空间 O(n)。如果 n 更大，可以用数组做递推或者记忆化来加速，但本题范围用纯递归完全够用。