数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

• 对于 $60\%$ 的数据，$N\le 50$；
• 对于 $100\%$ 的数据，$1\le N\le 5000$。

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
using namespace std;
using ll = long long;
const int N=2000;
int f[5][N];
int a[10];//存数组大小 
void jia(int t1,int t2,int t3){int len=max(a[t1],a[t2]);int jinwei=0;for(int i=0;i<len;i++){int t=f[t1][i]+f[t2][i]+jinwei;f[t3][i]=t%10;jinwei=t/10;}while(jinwei!=0){f[t3][len++]=jinwei%10;jinwei/=10;}a[t3]=len;//	reverse(f[t3],f[t3]+a[t3]);
}int n;
int main(){cin>>n;a[1]=1;a[2]=1;f[1][0]=1;f[2][0]=2;for(int i=1;i<=n;i++){jia(i%3,(i+1)%3,(i+2)%3);	}reverse(f[n%3],f[n%3]+a[n%3]);for(int i=0;i<a[n%3];i++)cout<<f[n%3][i];return 0;
}