从爬楼梯认识递推关系——一步步找到规律，写出代码

你有没有遇到过这样的问题：一件事情有很多种做法，但直接数数又容易数漏？比如，小明上楼梯，每次可以跨1级或者2级，问他爬到第n级台阶有多少种不同的走法？这个问题看着简单，但直接列举会很麻烦，尤其当n很大的时候。其实，我们可以用一种叫递推的方法，从小问题一步步推到大问题，像搭积木一样，又快又准。

一个有趣的问题（回顾）

小明去爬楼梯，他每次可以跨1级台阶，也可以跨2级台阶。请问：他要爬到第n级台阶，一共有多少种不同的走法？

比如，到第1级只有1种走法（直接跨1步）。到第2级，可以一次跨2步，也可以分两次各跨1步，所以有2种走法。那么到第3级呢？你可以试着列举出来：1+1+1，1+2，2+1，一共3种。到第4级呢？……

发现隐藏的规律

要数清楚到第n级有多少种走法，我们不要从第一级开始想，而是反过来想最后一步是怎么走的。这样就把一个大问题，拆成了两个小问题。

• 情况一：如果小明最后一步跨了1级，那么他之前一定站在第 n-1 级台阶上。所以，所有“最后一步跨1级”的走法数量，正好等于爬到第 n-1 级的走法总数。
• 情况二：如果小明最后一步跨了2级，那么他之前站在第 n-2 级台阶上。同理，这类走法的数量，等于爬到第 n-2 级的走法总数。

因为小明的最后一步只能选这两种情况（不能同时跨1和2），所以爬到第n级的总走法数，就是把这两种情况加起来：

到第n级的走法总数 = 到第n-1级的走法数 + 到第n-2级的走法数

我们用 f(n) 表示爬到第n级的走法数，就写成了：

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

这个式子就叫递推关系式。它告诉我们：知道前两个数，就能算出后一个数，像多米诺骨牌一样一个接一个倒下去。

生活中的类比
假设你每天存零花钱，第一天存1元，第二天存2元，之后每天存的钱数等于前一天加前两天的和。那么第三天存1+2=3元，第四天存2+3=5元……这个规律和爬楼梯一模一样。

别忘了起点——边界条件

光有递推公式还不够，还需要知道最开头几个台阶的走法，不然我们没法开始算。比如：

• 爬到第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，以此类推。

注意：有些同学会想，能不能从第0级开始？理论上 f(0) 可以看成1（站在地上不动，算一种“走法”），但这样 f(2)=f(1)+f(0)=1+1=2 也成立，不过对初学者来说，从第1级和第2级开始更直观。我们这里就用 f(1)=1, f(2)=2。

把规律变成C++代码

有了递推公式和边界条件，写代码就像做填空题。我们用一个循环，从第3级开始，每次用前两个数算出下一个数。

方法一：用三个变量滚动（省内存）

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数n：";
    cin >> n;

    // 处理特殊情况
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (n == 2) {
        cout << 2 << endl;
        return 0;
    }

    // 用三个变量递推：a存f(n-2)，b存f(n-1)，c存f(n)
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;   // 递推公式
        a = b;       // 向前移动：新的f(n-2)变成原来的f(n-1)
        b = c;       // 新的f(n-1)变成算出来的f(n)
    }
    cout << "爬到第" << n << "级有" << c << "种方法" << endl;
    return 0;
}

运行一下：输入3，输出3；输入4，输出5；输入5，输出8。神奇吧！

方法二：用数组存所有结果（更直观，适合初学者理解）

如果你觉得三个变量绕来绕去不好理解，可以开一个数组，把每个台阶的走法数都存起来，这样下标和台阶号一一对应，更清楚。

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数n：";
    cin >> n;

    // 创建一个足够大的数组，下标从1开始用
    int ways[100] = {0};  // 假设n不超过99
    ways[1] = 1;  // 到第1级有1种走法
    ways[2] = 2;  // 到第2级有2种走法

    for (int i = 3; i <= n; i++) {
        ways[i] = ways[i-1] + ways[i-2];  // 递推公式
    }
    cout << "爬到第" << n << "级有" << ways[n] << "种方法" << endl;
    return 0;
}

两种方法都可以，用数组的好处是每一步的结果都能看到，调试方便；用三个变量的好处是省空间，计算大n时更快。

新手经常犯的3个错误

错误1：忘记处理n=1或n=2的特殊情况

如果输入n=1，循环就不执行，直接输出一个未初始化的变量，结果会乱码。所以必须加上if判断，或者在数组里先赋值好。

错误2：变量更新顺序写反了

// 错误写法
c = a + b;
b = c;   // 先更新b
a = b;   // 然后a和b变成一样的了！

这样a被覆盖了，下一轮计算就错了。正确顺序是：先用a和b算出c，然后先移动a，再移动b。

错误3：数组下标越界

如果用数组，一定要确保数组大小够用。比如你声明 int ways[100]，但输入n=1000，就会访问非法内存，程序崩溃。对于比赛，可以开一个更大的数组（比如 int ways[100000]），或者用vector。

完整可运行示例（带多种测试）

下面是一个完整的代码，你可以复制到电脑上直接运行。它会问你台阶数，然后输出结果。

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数 n (1~90): ";
    cin >> n;

    // 用数组存储，注意n较大时结果会很大，这里用int只适合小n
    // 如果n>90，结果超出int范围，需要用long long或高精度
    long long ways[100] = {0};  // 用long long可以算到n=90左右
    ways[1] = 1;
    ways[2] = 2;

    for (int i = 3; i <= n; i++) {
        ways[i] = ways[i-1] + ways[i-2];
    }

    cout << "爬到第 " << n << " 级有 " << ways[n] << " 种方法。" << endl;
    return 0;
}

你可以试几个不同的n：

• n=1 → 1
• n=2 → 2
• n=3 → 3
• n=4 → 5
• n=5 → 8
• n=10 → 89

发现没？这个数列其实就是著名的斐波那契数列（只不过通常斐波那契从1,1开始，这里是1,2开始）。

递推思路还能用在哪儿？

学会了爬楼梯的递推，许多类似问题你都能自己解决。比如：

• 走棋盘：从左上角走到右下角，每次只能向右或向下，有多少种走法？
• 铺砖问题：用1×2或2×1的砖铺满2×n的地面，有多少种铺法？
• 零花钱计划：每天零花钱是前两天的和，问第n天有多少钱？

这些问题的核心都是：找到最后一步的来源，列出递推关系，再确定边界。递推是动态规划（DP）的入门基础，以后学DP时会发现，差不多所有DP问题都要先找出递推关系式。

如果你觉得意犹未尽，可以继续学习：

• 斐波那契数列的通项公式（直接算出结果，不用循环）
• 更高阶的递推（比如每次可以走1、2、3级，递推公式变成f(n)=f(n-1)+f(n-2)+f(n-3)）
• 记忆化递归（用递归+缓存来避免重复计算）

现在，拿起笔自己试着推导一下：如果小明每次可以走1级或3级，递推公式会变成什么样？边界条件呢？试试看！