#70 Climbing Stairs

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Intuition

To reach step n, you either came from step n-1 (one step) or step n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2), which is the Fibonacci recurrence.

Approach

1. Handle base cases: ways(1) = 1, ways(2) = 2.
2. Iterate from 3 to n, computing each step from the two previous values.
3. Only store the last two values to achieve constant space.

Solution

function climbStairs(n: number): number {
  if (n <= 2) return n;

  let prev2 = 1;
  let prev1 = 2;

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

  return prev1;
}

Complexity Analysis