4.23.1 — Climbing Stairs

LeetCode 70 · Easy · ★ Blind 75

The problem

You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways are there to reach the top?

n = 2  →  2     (1+1, or 2)
n = 3  →  3     (1+1+1, 1+2, 2+1)

The pattern

Ask the question backwards: how did you arrive at step n?

There are only two possibilities. You came from step n − 1 with a single step, or from step n − 2 with a double step. Those two groups do not overlap and cover everything, so:

\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2)

That is Fibonacci. The base cases are ways(1) = 1 and ways(2) = 2.

"How did I get here" is the question that produces almost every 1-D DP recurrence. Ask it before writing anything.

The four forms, on one problem

This problem is small enough to show all four forms from 4.22 side by side. Every other DP problem is one of these shapes with a harder recurrence.

Form 1 — memoised recursion.

def climbStairs(self, n: int) -> int:
    from functools import lru_cache

    @lru_cache(None)
    def ways(step: int) -> int:
        if step <= 2:
            return step
        return ways(step - 1) + ways(step - 2)

    return ways(n)

Write the plain recursion, add a cache. O(n) time and space, plus the call stack. lru_cache is Python's built-in memoisation decorator and is worth knowing.

Form 2 — full table.

dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]

The recursion's parameter became the array index. The loop goes upwards because dp[i] reads smaller indices.

Forms 3 and 4 — two variables. Since dp[i] only reads the previous two cells, the array is unnecessary.

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev, curr = 1, 2                    # ways(1), ways(2)
        for _ in range(3, n + 1):
            prev, curr = curr, prev + curr

        return curr

TypeScript

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

  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }

  return curr;
}

O(n) time, O(1) space.

The simultaneous assignment matters. prev, curr = curr, prev + curr evaluates the whole right-hand side first. Writing it as two statements would overwrite prev before prev + curr is computed. In JavaScript the destructuring assignment does the same job; without it you need a temporary.

Complexity

O(n) time, O(1) space.

There is also an O(\log n) solution using matrix exponentiation on the Fibonacci recurrence, and a closed form using the golden ratio — which loses precision for large n. Worth naming; not worth writing.

Why this problem is worth more than it looks

It is the smallest possible complete DP, so it is the one to use when you are deriving the method rather than the answer. If you can produce all four forms for this, the machinery is in place and every harder problem is just a harder recurrence.

And it establishes the counting rule: ways to reach a state = sum of the ways to reach every state that leads to it. Counting problems add; optimisation problems take a minimum or maximum. Which operator you use is the only difference between "how many ways" and "the cheapest way".

Where this goes next

• Min Cost Climbing Stairs — same two moves, but minimising a cost instead of counting. + becomes min. 4.23.2.
• Climbing with steps of 1, 2 or 3 — three terms instead of two.
• Climbing with an arbitrary step set — sum over every allowed step size, which is Combination Sum IV, and the same recurrence.
• Decode Ways — the same "one or two at a time" structure, with validity conditions attached. 4.23.7.
• Unique Paths — the two-dimensional version: arrive from the left or from above. 4.24.1.

What the interviewer will push on

"Derive the recurrence." Ask how you arrived at step n. Two disjoint cases that cover everything.

"What are the base cases?" ways(1) = 1, ways(2) = 2. Check them by hand; a great many wrong DP solutions are correct recurrences with wrong bases.

"Can you do it in O(1) space?" Two variables.

"What if you could take up to k steps?" Sum the previous k values. A sliding window sum keeps it O(n) rather than O(nk).

"Can you do better than O(n)?" Matrix exponentiation, O(\log n).

One thing to volunteer: say "this is Fibonacci" as soon as you have the recurrence. Recognising a known sequence is faster and more convincing than deriving the code.

Next: 4.23.2 Min Cost Climbing Stairs — the same two moves, optimising instead of counting.