53. Climbing Stairs

A staircase has n steps. On each move you go up either 1 step or 2 steps.

Return how many different sequences of moves bring you from the bottom to exactly the top step.

Example 1

Input: n = 2
Output: 2

Explanation: Either two single steps (1 + 1) or one double step (2).

Example 2

Input: n = 3
Output: 3

Explanation: The sequences are 1 + 1 + 1, 1 + 2 and 2 + 1.

Example 3

Input: n = 5
Output: 8

Constraints

1 <= n <= 45

Follow-up: Can you get it in O(log n) time? (Hint: the recurrence can be written as a 2×2 matrix power.)

💡 Hint 1

Think about the very last move. It was either a 1-step from step n - 1 or a 2-step from step n - 2.

💡 Hint 2

So ways(n) = ways(n - 1) + ways(n - 2). Computing this recursively without caching repeats a lot of work.

💡 Hint 3

You only ever need the previous two values, so two variables are enough.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Every way to reach step n ends with either a 1-step (from n - 1) or a 2-step (from n - 2), and those two groups never overlap, so ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. That is the Fibonacci recurrence. Build it bottom-up while keeping only the last two values.

Time O(n)Space O(1)

function climbStairs(n) {
  let prev = 1; // ways(i - 1)
  let curr = 1; // ways(i)
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

class Solution {
    public int climbStairs(int n) {
        int prev = 1, curr = 1;
        for (int i = 2; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit