信息奥赛题解｜爬楼梯

🚀 题目浏览

【题目描述】

树老师爬楼梯，他可以每次走 $1$ 级或者 $2$ 级，输入楼梯的级数，求不同的走法数。

例如：楼梯一共有 $3$ 级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共 $3$ 种方法。

【输入】

输入包含若干行，每行包含一个正整数 $N$，代表楼梯级数，$1≤N≤30$。

【输出】

不同的走法数，每一行输入对应一行输出。

【输入样例】

5
8
10

【输出样例】

8
34
89

【原题链接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1204

☘️ 题解分析

爬楼梯问题也是 递推思想 的典型体现。

我们可以把走到第 i 级楼梯的方案数 f[i] 看成 一个集合，由「最后一步走 1 级楼梯的方案数 f[i-1] 」和「最后一步走 2 级楼梯的方案数 f[i-2] 」这 两个子集 构成。

比如走到第 5 级楼梯的方案数 f[5] ，按照最后一步走的级数可以分为以下两个子集：

最后一步走 1 级，那么走最后一步之前，我们处在第 4 级台阶，所以这个子集的大小为 f[4]
最后一步走 2 级，那么走最后一步之前，我们处在第 3 级台阶，所以这个子集的大小为 f[3]

这样的分割方法做到了 不重复、不遗漏，因此只需按照方程 f[i] = f[i-1] + f[i-2] 去递推即可。

❗️ 误区提示

此题的一个 常见错误，就是把递推方程书写成 f[i] = f[i-1] + 2*f[i-2]。

这是因为在划分子集时，把第二个子集「最后一步走 2 级」✅ 误解成了「最后一步走 2 级有多少种方案」❌

这就导致在考虑 f[i-2] 时，认为 最后一步走 2 级有 2 种方案：即一次走 2 级，或先走 1 级，再走 1 级。把 f[i-2] 与 f[2] 产生了联系，所以在 f[i-2] 前乘了 2。❌

但是仔细思考，我们会发现上面这种错误的想法，本质上是因为两个子集出现了重复。

「最后一步走 2 级，但是每次走 1 级」的方案，其实是包含在第一个子集「最后一步走 1 级」中的。因为如果先走 1 级，再走 1 级，那最后一步就是 1 级，根本不能划分在「最后一步走 2 级」这个子集中，从而产生了错误。

也就是说，f[i-2] 与 f[2] 是没有关系的❗️

初学者在初学时犯了这种错误后，需要仔细思考原因，避免下次再走入这个误区。🍀

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 35;
int tmp;
int f[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i < N; ++i) {
        f[i] = f[i - 1] + f[i - 2];  //最后一步走1级的方案 + 最后一步走2级的方案
    }

    while (cin >> tmp) {
        cout << f[tmp] << endl;
    }

    return 0;
}