楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入输出格式

输入格式：

 

一个数字，楼梯数。

 

输出格式：

 

走的方式几种。

 

输入输出样例

输入样例#1：

4

输出样例#1：

5

说明

用递归会太慢，需用递推

（60% N<=50 ,100% N<=5000)

思路：高精+斐波那契数列

代码实现：

1 #include
     
       2 int n,al,bl,cl; 3 int a[3000],b[3000]={
   1},c[3000]; 4 int main(){ 5     scanf("%d",&n); 6     if(n==0){printf("0\n");return 0;} 7     for(int k=1;k<=n;k++){ 8         cl=bl; 9         for(int i=0;i<=cl;i++){10             c[i]+=a[i]+b[i];11             if(c[i]>9){12                 c[i+1]+=1;13                 c[i]%=10;14                 if(i==cl) cl++;15             }16         }17         al=bl;18         for(int i=0;i<=al;i++) a[i]=b[i];19         bl=cl;20         for(int i=0;i<=bl;i++) b[i]=c[i],c[i]=0;21     }22     for(int i=bl;i>=0;i--)23     printf("%d",b[i]);24     printf("\n");25     return 0;26 }
     

题目来源：洛谷