9.1 Fibonacci Style / Climbing Stairs

Demo: Climbing Stairs — LC 70 (Easy — Google/Amazon High)

Statement (Demo): A staircase has n steps and you climb 1 or 2 steps at a time. Return the number of distinct ways to reach the top. Example: n=3 → 3 (1+1+1, 1+2, 2+1) | ⚡ 1 ≤ n ≤ 45

Approach: Step i is reached from i-1 (one step) or i-2 (two steps), so dp[i] = dp[i-1] + dp[i-2]. Only the last two values matter, so space is O(1).

function climbStairs(n) {
  let prev = 1,
    cur = 1; // dp[0], dp[1]
  for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];
  return cur;
}

Complexity: Time O(n), Space O(1)