Climbing Stairs0/59 done
Part 2 · Problems · Simple DP

Climbing Stairs

#70 · Easy · LeetCode

You climb 1 or 2 steps at a time. How many distinct ways to reach step n?

n = 2 -> 2
n = 3 -> 3
n = 5 -> 8

Ask before coding

Hint

To reach step n, your last move came from n-1 or n-2.

Approach

ways(n) = ways(n-1) + ways(n-2). It's Fibonacci. Keep only the last two values.

Time O(n)   Space O(1)

Watch it run
Solution (JavaScript, tested)
function climbStairs(n) {
  // ways(n) = ways(n-1) + ways(n-2), keep only the last two
  let a = 1,
    b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

Traps

Say out loud: The last step was either one or two, so the answer is the sum of the two before. Bottom up with two variables.