Climbing Stairs Problem – Counting Ways to Reach the Top ????♂?

Problem Statement

Given a staircase with n steps, determine the number of distinct ways to reach the top. You can either climb 1 step or 2 steps at a time.

Example Calculations:

• n = 1 → 1 way → (1)
• n = 2 → 2 ways → (1,1), (2)
• n = 3 → 3 ways → (1,1,1), (1,2), (2,1)
• n = 4 → 5 ways → (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)

Mathematical Pattern – Fibonacci Approach

At any step n, you can only arrive from step n-1 or n-2.

Thus, the total ways to reach step n is the sum of the ways to reach the previous two steps:

climbingStaircase(n) = climbingStaircase(n-1) + climbingStaircase(n-2)

const climbingStaircase = n => {
  const noOfWays = [1, 2];
  for (let i = 2; i < n; i++) {
    noOfWays[i] = noOfWays[i - 1] + noOfWays[i - 2];
  }
  return noOfWays[n - 1];
};

console.log(climbingStaircase(1));
console.log(climbingStaircase(2));
console.log(climbingStaircase(3));
console.log(climbingStaircase(4));
console.log(climbingStaircase(5));        

Time Complexity: O(n)

• We iterate once from 3 to n, making it efficient.
• Space complexity is O(1) since we use only two variables.