题目描述

一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案

样例

输入：5

输出：8

思路

设$F(x)$表示从第0阶上到第x阶的走法数，根据最后一步的走法分成两类：

1）先从第0阶上到第x-1阶，最后一步上一阶；

2）先从第0阶上到第x-2阶，最后一步上两阶。

故由计数原理知$F(x)=F(x-1)+F(x-2)$，并且容易得到$F(1)=1, F(2)=2$，由此可以构造递归

C++ 代码

#include <iostream>

using namespace std;

int stair(int x)
{
    if(x == 1)return 1;
    else if(x == 2)return 2;
    else return stair(x - 1) + stair(x - 2);
}

int main()
{
    int n;

    cin >> n;

    cout << stair(n) << endl;

    return 0;
}