Overview

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

Implement climbStairs(n).

Constraints

• 1 ≤ n ≤ 45
• Return the count of distinct ways.
• Aim for $O(n)$ time, $O(1)$ space.

Examples

climbStairs(2);
// → 2  — (1+1) or (2)

climbStairs(3);
// → 3  — (1+1+1), (1+2), (2+1)

climbStairs(5);
// → 8

Notes

• This is the Fibonacci sequence. To reach step n, you either came from step n-1 (one step) or step n-2 (two steps).
• ways(n) = ways(n-1) + ways(n-2) with base cases ways(1) = 1, ways(2) = 2.
• Use two variables instead of an array for $O(1)$ space.

Solution

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

  let prev2 = 1;
  let prev1 = 2;

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

  return prev1;
}

Resources

• Climbing Stairs — LeetCode
• Fibonacci Sequence — Wikipedia