题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
输入样例#1：4
输出样例#1：
5
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
啊啊，数据太大了！
肿么办？！
当数据等于5000时的斐波那契数为
62763028004889570860352531083496840554785287027364574390258244489279372568116632644758837115278062503299846902498468198006485800830401075847103326875965621850736404222867992399326157971059747108570954873428203513074771418750121768743071560162299658325891377797249738543627776298782295055002604771361083637090900104215369154886323392407569879741225986035919203068749267556003618653543304446819151546957418519600710899440153193001285741076627570547906481527513664755291218772127854896651017337558985803179844029638737381870001207378241931639947424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
long long 也开不开啊！
那真么办？！
用高精啊！！！
代码
#include<cmath>#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;int f[5001][5001]={0},len[5001]={0};int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}void fei(int a,int b,int c){for(int i=1;i<=max(len[b],len[c]);i++){f[a][i]+=f[b][i]+f[c][i];if(f[a][i]>9){f[a][i+1]+=f[a][i]/10;f[a][i]%=10;len[a]=max(len[a],i+1);}else len[a]=max(len[a],i);}}int main(){int n=read();f[1][1]=1;f[2][1]=2;len[0]=1;len[1]=1;for(int i=3;i<=n;i++){fei(i,i-1,i-2);}for(int i=len[n];i>=1;i--)cout<<f[n][i];return 0;}
如果觉得《数楼梯——恶心的高精斐波那契数列》对你有帮助，请点赞、收藏，并留下你的观点哦！
