题目描述

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

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

输入输出格式

输入格式：

 

一个数字，楼梯数。

 

输出格式：

 

走的方式几种。

 

输入输出样例

输入样例#1：

4

输出样例#1：

5

说明

用递归会太慢，需用递推

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

 

 

啊啊，数据太大了！

肿么办？！

当数据等于5000时的斐波那契数为

6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626

 

long long 也开不开啊！

那真么办？！

用高精啊！！！

 

 

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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<