hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Climbing Stairs
Problem: 70. Climbing Stairs
Problem Link: https://leetcode.com/problems/climbing-stairs/
Approach:
The ways to reach the Nᵗʰ step depends on the sum of ways to reach step N-1 and N-2.
It illustrates the famous Fibonacci number. (https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)
Initiate two variable say, previous_of_current and previous_of_previous, that holds the total ways to reach step N-1 and N-2.
Now, keep moving till reaching step N.
And while moving add previous_of_current and previous_of_previous and assign them to another variable say, current, which holds the ways to reach step N.
Return the value of previous_of_current as it holds the finally reached value.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
class Solution {
public:
int climbStairs(int n) {
int previous_of_current = 1, previous_of_previous = 1, current;
for(int i=2; i<=n; i++){
current = previous_of_previous + previous_of_current;
previous_of_previous = previous_of_current;
previous_of_current = current;
}
return previous_of_current;
}
};