跳台阶

题目描述

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

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

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

数据范围
1≤n≤15
输入样例：

5

输出样例：

8

思路

dfs

C++ 代码

#include <iostream>

using namespace std;

int ans,n;
void dfs(int k)
{
    if( k == n ) ans++;
    else if( k < n )
    {
        dfs( k + 1);
        dfs( k + 2);
    }
    
}

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