洛谷 P1255 数楼梯 70

题目描述

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

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

输入输出格式

输入格式：

一个数字，楼梯数。

输出格式：

走的方式几种。

输入输出样例

输入样例#1：

输出样例#1：

说明

用递归会太慢，需用递推

（60% N<=50 ,100% N<=5000)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cstring>
 6 #include<string>
 7 
 8 using namespace std;
 9 
10 int a[5001],b[5001],c[5001];
11 
12 inline void read(int &x)
13 {
14     char c=getchar();
15     x=0;
16     while(c<'0'||c>'9')c=getchar();
17     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
18 }
19 
20 int main()
21 {
22     int n,len;
23     read(n);
24     a[1]=1;a[0]=1;
25     b[1]=1;b[0]=1;
26     for(int k=2;k<=n;k++)
27     {
28         len=b[0];
29         for(int i=1;i<=len;i++)
30         {
31             c[i]=a[i]+b[i];
32         }
33         for(int j=1;j<=len;j++)
34         {
35             c[j+1]+=c[j]/10;
36             c[j]=c[j]%10;
37         }
38         if(c[len+1]==1)
39         {
40             len++;
41         }
42         c[0]=len;
43         memcpy(a,b,1000*sizeof(int));
44         memcpy(b,c,1000*sizeof(int));
45     }
46     for(int i=c[0];i>=1;i--)
47     {
48         if(i==c[0]&&c[c[0]]==0)
49             continue;
50         printf("%d",c[i]);
51     }
52     return 0;
53 }