总时间限制: 1000ms 单个测试点时间限制: 500ms 内存限制: 65536kB

描述

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。

输入

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 ≤ N ≤ 30

输出

不同的走法数，每一行输入对应一行输出

样例输入

5
8
10

样例输出

8
34
89

思路

千里之行始于足下，对于第一步，我们有2种情况：

• 第一步走1级，剩下 (n - 1) 级
• 第一步走2级，剩下 (n - 2) 级

我们可以发现：n级台阶的走法 = 先走一级，n-1级台阶的走法 + 先走2级，n-2级台阶的走法

即递推公式为： %20%3D%20f(n%20-%201)%20%2B%20f(n%20-%202)#card=math&code=f%28n%29%20%3D%20f%28n%20-%201%29%20%2B%20f%28n%20-%202%29)

本题的边界条件为： %20%3D%20%5Cbegin%7Bcases%7D0%2C%20%26n%3C0%5C%5C%201%2C%20%26n%20%3D%200%5C%20or%5C%201%5C%5C%202%2C%20%26n%20%3D%202%20%5Cend%7Bcases%7D#card=math&code=f%28n%29%20%3D%20%5Cbegin%7Bcases%7D0%2C%20%26n%3C0%5C%5C%201%2C%20%26n%20%3D%200%5C%20or%5C%201%5C%5C%202%2C%20%26n%20%3D%202%20%5Cend%7Bcases%7D)

显而易见，这是一个 Fibonacci数列.

代码

#include <iostream>
using namespace std;
int N;
int stairs(int n) {
    if( n < 0 )  return 0;
    if( n == 0 )  return 1;
    return stairs( n-1 ) + stairs( n-2 );
}
int main() {
    while( cin >> N ) {
        cout << stairs(N) << endl;
    }
    return 0;
}