題目描述

一個(gè)樓梯共有 nn 級臺階，每次可以走一級或者兩級，問從第 00 級臺階走到第 nn 級臺階一共有多少種方案。

輸入格式
共一行，包含一個(gè)整數(shù) nn。

輸出格式
共一行，包含一個(gè)整數(shù)，表示方案數(shù)。

數(shù)據(jù)范圍
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;
}