题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
走的方式几种。
输入输出样例
输入： 4 输出： 5
说明/提示
60% N<=50
100% N<=5000)
下面正式进入这道题的题解
我今天写了两篇题解（都很水）
这道题的话似乎有很多种方法，只是我见过的就好几种
这里就像大家推荐两种方法喽。
第一种解法
第一种解法是根据题意直接递归（推）（个人感觉是一种了）
我们想一下，走楼梯，要么一次走一格，要么一次走两格，那我每次的走法就等于=上一格的方案数+上上格的方案数咯，这就推出了方程：
f[n]=f[n-1]+f[n-2]
OK结束啦。
但是要注意走到第n-1阶的时候就不能再迈两阶了。
这里就展示一种递归的解法：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define inf 100000000 7 using namespace std; 8 int ans,n,a; 9 int dg(int x) 10 { 11 if(x<=0) 12 return 1; 13 if(x-2>=0) 14 return dg(x-2)+dg(x-1); 15 else 16 return dg(x-1); 17 } 18 int main() 19 { 20 cin>>a; 21 ans=dg(a); 22 cout<<ans<<" "; 23 }
第二种解法
同学们把代码提交上去之后就会发现会t掉或者wa（递归会t递推没试过）
wa的原因是因为数据大，需要高精度
tle因为递归的时间太长，数据太大。所以不可行（其实不是，在每一次计算出第x阶是记录下来方案数，下次直接用就可以，这里不写了）
所以就要想起其他方法：
高精加+斐波那契数列（一种正解）
为什么会得出这个结论（我当时是打表找规律）
其实大家看斐波那契数列的公式：f(n)=f(n-1)+f(n-2)
和这道题一样的！
所以直接这么办就好（二维数组要用上）
高精不会写？这里不教。。。。。。
上代码！
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define inf 100000000 7 using namespace std; 8 int n,len=1,a[5010][5010]; 9 int p(int j) 10 { 11 for(int i=1;i<=len;i++) 12 a[j][i]=a[j-1][i]+a[j-2][i]; 13 for(int i=1;i<=len;i++) 14 { 15 if(a[j][i]>=10) 16 { 17 a[j][i+1]+=a[j][i]/10; 18 a[j][i]=a[j][i]%10; 19 if(a[j][len+1]==1) 20 len++; 21 } 22 } 23 } 24 int main() 25 { 26 cin>>n; 27 a[1][1]=1,a[2][1]=2; 28 for(int i=3;i<=n;i++) 29 p(i); 30 for(int i=len;i>=1;i--) 31 cout<<a[n][i]; 32 return 0; 33 }
好了结束啦！
最后祝大家AC所有题！
客官，给个赞再走呗！
.JPG)
