You are given a stair with ` n `

steps,and you are currently at `0`

^{th} stair. From each point in the stair, you can climb either 1 stair or you can climb 2 stairs. You need to output the number of ways in which you can reach step ` n `

.

#### Example Test Cases

##### Sample Test Case 1

Input grid: ` 2 `

Expected Output: ` 2 `

Explanation: You can climb till step ` 2 `

in the following ways:

- 1 step + 1 step
- 2 step

##### Sample Test Case 2

Input grid: ` 3 `

Expected Output: ` 3 `

Explanation: You can climb three steps in the following ways:

- 1 step + 1 step + 1 step
- 1 step + 2 steps /li>
- 2 steps + 1 step

#### Solution

We can easily solve this problem using recursion. To reach ` n `

^{th} step, the last step will either be taken from ` n - 2 `

step or from ` n - 1`

step. Therefore, the no of ways for reaching `n`

^{th} step is sum of no of ways of reaching ` n -2 `

step + the number of ways of reaching ` n - 1 `

step.

Therefore, if we model the above solution in the form of a recursive equation, it would look like this: ` f(n) = f(n - 1) + f(n-2) `

The above equation is the recursive equation for fibonacci numbers which we can compute very easily as shown in the below code:

#### Implementation

#include <bits/stdc++.h> using namespace std; int climbStairs(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 2; int t1 = 1, t2 = 2, t3 = 3; int i = 3; while (i < n) { t1 = t2; t2 = t3; t3 = t1 + t2; i++; } return t3; } int main() { int n = 5; cout << "No of ways to climb " << n << " stairs is " << climbStairs(n) << "\n"; }