📚 爬楼梯问题
🚀 题目浏览
【题目名称】爬楼梯
【题目描述】
树老师爬楼梯，他可以每次走
1
1
1 级或者
2
2
2 级，输入楼梯的级数，求不同的走法数。
为林口等地区用户提供了全套网页设计制作服务，及林口网站建设行业解决方案。主营业务为
网站设计、网站建设、林口网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
例如：楼梯一共有
3
3
3 级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共
3
3
3 种方法。
【输入】
输入包含若干行，每行包含一个正整数
N
N
N，代表楼梯级数，
1
≤
N
≤
30
1≤N≤30
1≤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;
}
✍️ 写在最后
如果各位小伙伴觉得博主的题解写的不错，可以给本文 点个赞 👍
这样可以让 更加优质的文章 有 更大的概率 被推送到 搜索界面的榜首，为未来的小伙伴们节约更多搜索、阅读的成本。 🚀
同时，你的支持 也是我 不断创作 的动力。☘️
有想要看更多题解报告的小伙伴，也可以关注我的专栏「信息奥赛题解」。
我们下期再见。👋
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站栏目：【信息奥赛题解】爬楼梯（详细题解&C++代码）-创新互联
网站路径：
http://cdkjz.cn/article/cojepi.html
