• Published:

Given a staircase with n steps, you start at step 0 and may move either 1 step or 2 steps at a time. The task is to determine how many different ways there are to reach step n.

Problem

Input: a single integer n.

Output: a single integer, the total number of valid ways to go from step 0 to step n.

Constraints

1 ≤ n ≤ 15

Example

Input:

5

Output:

8

Idea

This can be viewed as a one-dimensional recursive search tree.

At every position, there are two possible choices:

  • move up 1 step
  • move up 2 steps

That means each step in the process can be treated like a node in a tree, and each recursive call branches into two directions.

  • If the current position reaches n, that path is valid, so the count increases by 1.
  • If the current position is still less than n, continue exploring both choices.
  • If it goes beyond n, that branch stops naturally because it no longer satisfies the recursive condition.

image

Recursive approach

Use a global variable ans to store the number of valid paths, and let ff(k) represent the recursive search starting from step k.

  • When k == n, one complete path has been found.
  • When k < n, recursively try k + 1 and k + 2.
  • Start the search from 0.

Code

#include <bits/stdc++.h>
using namespace std;

int ans=0,n;  //定义ans存储答案，n为满足答案的条件

void ff(int k){  //递归遍历
    if(k==n){  //满足答案ans++
        ans++;
    }
    else if(k<n){  //未到达条件时进行选择
        ff(k+1);
        ff(k+2);
    }
}

int main(){
    cin>>n;
    ff(0);  //从0开始递归
    cout<<ans;
    return 0;
}

Because n is at most 15, this direct recursive enumeration is enough for the problem.

Related Posts