楼梯有 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;

斐波那契数列的应用是从画图得知的规律

第一个台阶有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];

}