1742 爬楼梯

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

 

 

题目描述 

Description

小明家外面有一个长长的楼梯，共N阶。小明的腿很长，一次能跨过一或两阶。有一天，他突发奇想，想求出从最低阶到最高阶共有几种爬楼梯的方案。你帮帮他吧！

输入描述 

Input Description

一个整数N。

输出描述 

Output Description

一个整数，为方案总数。

样例输入 

Sample Input

5

样例输出 

Sample Output

8

数据范围及提示 

Data Size & Hint

0≤N≤40

 

思路：

1 2 3 5 8 13 21……

大佬们一定发现了这个题是斐波那契数列吧？！（好了，废话少说，我们来A题）

代码：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 100using namespace std;long long n,ans,f[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1; ch=getchar();}    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int main(){    n=read();    f[0]=1;f[1]=1;    for(int i=2;i<=n;i++)     f[i]=f[i-1]+f[i-2];    ans=f[n];    printf("%lld",ans);    return 0;}