 # Climbing Stairs

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";
}
```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.