You are given a stair with n
steps,and you are currently at
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 0
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
th step, the last step will either be taken from n
n - 2
step or from n - 1
step. Therefore, the no of ways for reaching
th step is sum of no of ways of reaching n
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"; }