Climbing StairsEasy

You're climbing a staircase of n steps. Each move you can climb 1 or 2 steps. How many distinct ways are there to reach the top?

Examples

Input: n = 3 → Output: 3 — (1+1+1), (1+2), (2+1)

Approach

Naive recursion re-derives the same subproblems over and over (ways to reach step 5 needs ways to reach step 3 multiple times through different branches), causing exponential blowup. This is fibonacci wearing a different costume: ways(n) = ways(n-1) + ways(n-2), because your last move to reach step n was either a 1-step from n-1 or a 2-step from n-2. Track just the last two results as you count upward, no recursion or array needed.

Complexity — best & worst case

Naive recursive — time O(2ⁿ)

Optimal (bottom-up) — time O(n), best and worst case are the same — always counts up to n

Optimal (bottom-up) — space O(1) — two rolling variables

Code

// You're climbing a staircase of n steps. Each move you can climb
// either 1 or 2 steps. How many distinct ways to reach the top?

// --- Brute force: recursion without caching, recomputes the same
// subproblems over and over — exponential blowup ---
function climbStairsBrute(n) {
  if (n <= 2) return n;
  return climbStairsBrute(n - 1) + climbStairsBrute(n - 2);
}

// --- Optimal: this is just fibonacci in disguise. Ways to reach step
// n = ways to reach (n-1) [then take 1 step] + ways to reach (n-2)
// [then take 2 steps]. Bottom-up with two rolling variables, O(1) space. ---
function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1; // ways to reach step 1
  let prev1 = 2; // ways to reach step 2

  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

// --- Example Usage ---
console.log(climbStairs(2));      // 2  -> (1+1), (2)
console.log(climbStairs(3));      // 3  -> (1+1+1), (1+2), (2+1)
console.log(climbStairs(5));      // 8
console.log(climbStairsBrute(5)); // 8, same answer, much slower for large n