题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
思路：数学+高精
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; struct nond{ int num[50000]; }f[5010]; void jia(int pos){ f[pos].num[0]=max(f[pos-1].num[0],f[pos-2].num[0]); for(int i=1;i<=f[pos].num[0];i++) f[pos].num[i]=f[pos-1].num[i]+f[pos-2].num[i]; for(int i=1;i<=f[pos].num[0];i++) if(f[pos].num[i]>=10){ if(i==f[pos].num[0]) f[pos].num[0]++; f[pos].num[i+1]+=1; f[pos].num[i]%=10; } for(;f[pos].num[0]>=1;f[pos].num[0]--) if(f[pos].num[f[pos].num[0]]) break; } int main(){ scanf("%d",&n); if(n==0){ cout<<"0";return 0;} f[1].num[1]=f[1].num[0]=f[0].num[0]=f[0].num[1]=1; for(int i=2;i<=n;i++) jia(i); for(int i=f[n].num[0];i>=1;i--) cout<<f[n].num[i]; }