Climbing Stairs LeetCode Solution
Climbing Stairs Leetcode Problem :
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example :
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Climbing Chairs Leetcode Problem Solution :
Constraints :
- 1 <= n <= 45
Example 1:
- Input: n = 3
- Output: 3
- Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Thus, the result should be [4,3,2,2]
Approach : Recursion
The recursive solution uses the concept of Fibonacci numbers to solve the problem. It calculates the number of ways to climb the stairs by recursively calling the climbStairs function for (n-1) and (n-2) steps.
Complexity:
Time Complexity:
Time complexity is (O(2^n)).
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
return climbStairs(n-1) + climbStairs(n-2);
}
};
Java
class Solution {
public int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
return climbStairs(n-1) + climbStairs(n-2);
}
}Python
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
return self.climbStairs(n-1) + self.climbStairs(n-2)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment