Count ways to reach nth stair

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

• The Geeks For Geeks solution at bottom tells it can be done in log(n) as well, and it is not going beyond n.

Approach

• Total ways(n) = ways(n-1) + way(n-2)
• overlapping_subproblems The person can reach nth stair by either n-1 stair or n-2 stair
• The above expression comes fromfibonaccirecursion_tree
• This problem can be solved bymatrix_exponentiation in log n time.

CodeBottom_Up

 
def countWays(n):
 
	climb_one_stair = 1 # possible number of ways to reach nth stair from n-1th stair
	climb_two_stair = 1 # possible number of ways to reach n-1 stair from n-2 stair
 
	for i in range(2, n+1):
		curr = climb_one_stair + climb_two_stair
		climb_two_stair = climb_one_stair
		climb_one_stair = curr
	return climb_one_stair
 
n = 4
print("Number of Ways : ", countWays(n))
 

Code in Javascript

	/** * @param {number} n * @return {number} */ 
var climbStairs = function(n) { 
	 let prv1 = 1; 
	 let prv2 = 1; 
																				 for (let i = 0; i < n; i++) { 													let tmp = prv1; 
		prv1 = prv1 + prv2; 
		prv2 = tmp; 
      } 
																			      return prv2; 
};

Problem Modification

• Instead of telling the number of ways, tell total number of stairs taken.

  function countStairsTaken(n) {
    if (n <= 1) {
        return n;
    }
   
    const stairsTaken = new Array(n + 1).fill(0);
    stairsTaken[1] = 1;
   
    for (let i = 2; i <= n; i++) {
        stairsTaken[i] = stairsTaken[i - 1] + 1;
    }
   
    return stairsTaken[n];

}

// Example usage const n = 9; const result = countStairsTaken(n); dv.paragraph(Number of stairs taken to reach step ${n}: ${result});

## Links
- https://www.geeksforgeeks.org/count-ways-reach-nth-stair/