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";
}