【华为练习题】 爬梯问题

题目

一个楼梯有N阶，从下往上走，一步可以走一阶，也可以走两阶，有多少种走法？

例如3阶楼梯有3种走法：

1、1、1

1、2

2、1

输入样例：

3

返回值样例：

3

分析

要爬上第N阶楼梯，有两种情况，从第N-1阶走一步或从第N-2阶走两步，得到递推式f(n)=f(n-1)+f(n-2)

解答

#include <iostream>
using namespace std;

int Stairs(int n){
    if (n <= 1) return 1;
    else return Stairs(n-1) + Stairs(n-2);
}

int main()
{
    int n;
    cin >> n;
    cout << Stairs(n) << endl;
    return 0;
}