📚 爬楼梯问题

🚀 题目浏览

【题目名称】爬楼梯

【题目描述】

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

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

【输入】

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

【输出】

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

【输入样例】

5
8
10

【输出样例】

8
34
89

【原题链接】

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

☘️ 题解分析

爬楼梯问题也是 递推思想 的典型体现，这里把 f[i] 的方案看成了 一个集合，由「最后走 1 步的方案 f[i-1] 」和 「最后走 2 步的方案 f[i-2] 」这 两个子集合 构成，做到了 不重复、不遗漏，因此只需按照方程 f[i] = f[i-1] + f[i-2] 去递推即可。

【误区提示❗️❗️❗️】

此问题容易产生的一个误区，就是把方程书写成 f[i] = f[i-1] + 2*f[i-2]。

这是因为在考虑问题时，把「最后一步走几步」✅ 误解成了「最后走几步有多少种方案」❌

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

仔细思考，我们会发现上面这种思想，本质上导致两个子集出现了重复，因为 「最后走 2 步中，每次走 1 步」的方案，其实是包含在 「最后走 1 步」中的，所以产生了错误。

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

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

🧑🏻‍💻 C++ 代码

#includeusing 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;
}

✍️ 写在最后

如果各位小伙伴觉得博主的题解写的不错，可以给本文 点个赞 👍

这样可以让 更加优质的文章 有 更大的概率 被推送到 搜索界面的榜首，为未来的小伙伴们节约更多搜索、阅读的成本。 🚀

同时，你的支持 也是我 不断创作 的动力。☘️

有想要看更多题解报告的小伙伴，也可以关注我的专栏「信息奥赛题解」。

我们下期再见。👋