HDOJ2041-超级楼梯（斐波拉契数列的应用）

Problem Description
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output
对于每个测试实例，请输出不同走法的数量

Sample Input
2
2
3

Sample Output
1
2

这题刚开始用的递归，但是超时了，后来在学斐波拉契数列数列时看到这是一个列子，于解了出来。

//time    memory
// 0 MS    1792K

#include <iostream>
using namespace std;

int data[45];

int f(int n)
{
    if(n<2)
    {
        return n;
    }
    if(data[n]!=-1)
    {
        return data[n];
    }
    else
    {
        data[n] = f(n-1) + f(n-2);
        return data[n];
    }
}

int main()
{
    int t;
    cin >> t;
    memset(data, -1, sizeof(data));
    while(t --)
    {
        int n;
        cin >> n;;
        cout << f(n) << endl;
    }
    return 0;
}