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


  • Approach:

    1. The ways to reach the Nᵗʰ step depends on the sum of ways to reach step N-1 and N-2.

    2. It illustrates the famous Fibonacci number. (https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

    3. Initiate two variable say, previous_of_current and previous_of_previous, that holds the total ways to reach step N-1 and N-2.

    4. Now, keep moving till reaching step N.

    5. 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.

    6. 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;

}

};