樓梯有 N?階，上樓可以一步上一階，也可以一步上二階。

編一個程序，計算共有多少種不同的走法。

輸入格式

一個數字，樓梯數。

輸出格式

輸出走的方式總數。

輸入輸出樣例

輸入

4

輸出?

5

• 對于?$60\%$?的數據，N≤50；

• 對于?$100\%$?的數據，1≤N≤5000。

時間限制1.00s

內存限制128.00MB

思路：

斐波那契數列的第50位是20365011074（11位數）

long long的數據范圍是-2147483648 到 2147483647（10位數）

明顯可以看出這道題不是簡單的遞歸/數組求斐波那契數列，要用到高精度算法

高精度算法（這里只說加法，b站上有很多詳細視頻）

主要代碼：

c[i]+=a[i]+b[i];

c[i+1]=c[i]/10;

c[i]=c[i]%10;

斐波那契數列的應用是從畫圖得知的規(guī)律

第一個臺階有1種可能；

第二個臺階有2種可能；

第三個臺階有3種可能；

第四個臺階有5種可能；……

易錯點：

1. ans數組不能是long long類型不然會超出內存限制

2. 看清楚不能用遞歸和數組求這道題
   

3. 注意數組的序號不要寫錯了，自己的代碼是從0開始的

代碼：

#include <iostream>

using namespace std;

int ans[5005][5005],len=1;

void jf(int k)

{

? ? for(int i=0;i<len;i++) ans[k][i]=ans[k-1][i]+ans[k-2][i];

? ? for(int i=0;i<len;i++)

? ? ? ? if(ans[k][i]>=10){

? ? ? ? ? ? ans[k][i+1]+=ans[k][i]/10;

? ? ? ? ? ? ans[k][i]=ans[k][i]%10;

? ? ? ? ? ? if(ans[k][len])len++;

? ? ? ? }

}

int main()

{

? ? int n;

? ? cin>>n;

? ? ans[0][0]=1,ans[1][0]=2;

? ? for(int i=2;i<n;i++) jf(i);

? ? for(int i=len-1;i>=0;i--)cout<<ans[n-1][i];

}