AcWing 821. 跳台阶 --递归思想

原题链接： https://www.acwing.com/problem/content/823/

/*题目： 一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。*/
#include <iostream>
using namespace std;
// 定义一个求斐波那契数列的函数
int fib(int n) {
    if (n == 1 || n == 2) return n;
    else return fib(n-1) + fib(n-2); //巧妙地使用递归就能解决这个问题了
}
int main(void) {
    /*
    * 1层台阶--1种跳法
    * 2层台阶--2种跳法（一次跳一层，一次跳两层）
    * 3层台阶-- 3种跳法 （1| 1 2 | 2 1）/
    * 4层台阶 -- 5种跳法 （2 2 | 1 1 1 1|2 1 1| 1 2 1| 1 1 2| ）
    * 5层台阶-- 8种跳法 （1 1 1 1| 2 2 1 |2 1 2| 1 2 2 | 1 1 1 2| 1 1 2 1 | 1 2 1 1| 2 1 1 1    | 
    * 6层台阶 -- 13种跳法
    * 列举后可以看出来其实这个问题的本质是一个斐波那契数列
    * F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
    */
    int n; //定义楼梯阶数
    cin >> n; //输入楼梯阶数
    cout << fib(n) << " " << endl; //输出方案数
    return 0;
}