题目描述

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

输入格式
共一行，包含一个整数n。

输出格式
共一行，包含一个整数，表示方案数。

数据范围

$1≤n≤15$

样例

输入样例：

$5$

输出样例：

$8$

DFS

C++ 代码

#include <iostream>

using namespace std;

int n,res;

void f(int u) //f(u)表示当前在第几层楼梯
{
    if(u >= n)
    {
        if(u == n) res ++; // 当成功上到第n层时记录一次方案
        return ;//当上到 n + 1层时 舍去此种方案
    }

    f(u + 1); //从当前楼层上一层
    f(u + 2); //从当前楼层上两层
}

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

状态转移

C++ 代码

#include <iostream>

using namespace std;

int f(int n)// f(n)表示到达第n层楼梯可用的方案数
{
    if(n == 0 || n == 1) return 1; // 初状态定义 表示当不动或是到达第1层楼梯时 有一种方案
    return f(n - 1) + f(n - 2); // 状态转移  表示第n层楼梯可由第 n - 1 层楼梯和 n - 2 层楼梯直接到达 故方案数到达二者时的方案数之和
}

int main()
{
    int n;
    cin >> n;
    cout << f(n) << endl;//f(n)即是答案
    return 0;
}