Climbing Stairs

Companies:

You are given a stair with n steps,and you are currently at 0th 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 nth 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.