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

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

输入格式

一个数字，楼梯数。

(相关资料图)

输出格式

输出走的方式总数。

输入输出样例

输入

4

输出 

5

对于 60%60% 的数据，N≤50；

对于 100%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种可能；……

易错点：

ans数组不能是long long类型不然会超出内存限制

看清楚不能用递归和数组求这道题

注意数组的序号不要写错了，自己的代码是从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];

}