本文主要是介绍dfs专题 P1255 数楼梯——洛谷（疑问），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
楼梯有 �N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入输出样例
输入 #1复制
4
输出 #1复制
5
说明/提示
- 对于 60%60% 的数据，�≤50N≤50；
- 对于 100%100% 的数据，1≤�≤50001≤N≤5000。
想法：
因为在复习dfs，所以想用dfs写，结果部分超时了，也剪了枝，不知道是dfs写不出来还是要进一步优化。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
void dfs(int x){
if(x==n) {
ans++;
return ;
}
else if(x>n) return ;
else if(x<n){
dfs(x+1);
if(x+2<=n)//剪枝
dfs(x+2);
}
}
int main(){
cin>>n;
dfs(0);
cout<<ans;
}
这篇关于dfs专题 P1255 数楼梯——洛谷（疑问）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
