题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例

输入 #1

4

输出 #1

5

说明/提示

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

分析：

斐波那契数列+高精度

假设要走到第 i 个楼梯，那么我们必须要先走到第 i-1 个楼梯或者第 i-2个楼梯，然后一步到第 i个楼梯，所以到第i个楼梯的走法总数 f[i] =f[i-1]+f[i-2]，依次类推，可以发现这是一个斐波那契数列，但斐波那契数列增长很快，我们必须用高精度来存，由于封装大整数结构体十分繁琐，这里使用一个取巧的方法，代码如下：
 

#include<iostream>
using namespace std;
const int N=6000;
int f[N][N];
int n,len;
void add(int x)
{
	for(int i=1;i<=len;i++)
	{
		f[x][i]=f[x-1][i]+f[x-2][i];
	}
	for(int i=1;i<=len;i++)
	{
		if(f[x][i]>=10) 
		{
			f[x][i+1]+=f[x][i]/10;
			f[x][i]%=10;
			if(f[x][len+1]) len++;
		}	
	}
}
int main()
{
	len=1;
	cin>>n;
	f[1][1]=1;
	f[2][1]=2;
	for(int i=3;i<=n;i++)
	{
		add(i);  
	}
	for(int i=len;i>=1;i--)
	{
		cout<<f[n][i];	
	}
	return 0;
 }