爬楼梯问题-最大迈两步

问题描述：

有n阶楼梯，每次只能迈一步或两步，输出有多少种迈法到达楼顶。

解题心得：

递归方法：先考虑最后一步，可能是迈了一步，可能是迈了两步。所以step(n)=step(n-1)+step(n-2)，然后step(0)=1，step(1)=1;

但是递归方法时间复杂度太高，n=40就已经需要一段时间了。

顺便学习了如何打表，把结果全部输出到一个txt文件里，然后需要哪个结果用哪个就行。

下面是代码：

#include 
#include 
//时间复杂度太大，不采用。
using namespace std;

int step(int n)
{
    if(n==0||n==1){
        return 1;
    }else{
        return step(n-1)+step(n-2);
    }
}

int main
{
    int n;
    FILE *fp;
    long long int a[55];
    fp=fopen("fibonaqi.txt","w");
    for(int i=0;i<40;i++){ ai='step(i);' fprintffplld\nai cin>>n;
    cout<<a[n];
    return 0;
}

fibonacci数列： a[i]=a[i-1]+a[i-2];每一步都可以由前面两步得到，正好是斐波那契数列。

#include 

using namespace std;

int main
{
    int a[55];
    int n;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<53;i++){ ai='a[i-1]+a[i-2];' cin>>n;
    cout<<a[n];
    return 0;
}