题目 1400: 教学楼的楼梯题解

1.解题思路

第n层楼可以从第n-1层楼迈一步或从第n-2层楼迈两步，所以有f(n)=f(n-1)+f(n-2)种走法，用数组f表示，也可以用递推，但是时间超限了。

2.参考代码

2.1.数组法

#include<iostream>
using namespace std;
int t,n,i,f[45];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        f[1]=f[2]=1;
        for(i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];
        cout<<f[n]<<endl;
    }
    return 0;
}

2.2.（仅用于参考）递推法

#include<iostream>
using namespace std;
int t,n;
int f(int n){
    if(n<3) return 1;
    return f(n-1)+f(n-2);
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        cout<<f(n);
    }
    return 0;
}