LeetCode #70 Easy

Climbing Stairs

You climb a staircase of n steps, moving either 1 or 2 steps at a time. Return the number of distinct ways to reach the top.

dynamic-programmingrecursionmaths

Open on LeetCode ↗

02

Intuition

💡

Ask not how to get to the top, but how you arrived at the last step. Your final move was either a 1-step (so you were at n-1) or a 2-step (so you were at n-2) — there is no third option. Those two cases are disjoint, because the final move differs, so the counts simply add: dp[n] = dp[n-1] + dp[n-2]. Everything else is choosing base cases and deciding whether to build the answer downward with recursion or upward with a loop.

03

Approach

1

Find the recurrence by looking at the last move

Let f(i) be the number of ways to reach step i. Every path to i ends with exactly one move, and that move is either +1 or +2. Paths ending in +1 are in bijection with paths to i-1; paths ending in +2 with paths to i-2. No path is in both sets, since the last move is fixed. Therefore f(i) = f(i-1) + f(i-2) — the Fibonacci recurrence, arrived at from the problem rather than recognised from memory.

2

Pin down the base cases

f(1) = 1: one way, a single step. f(0) = 1: there is exactly one way to already be where you are — do nothing. Setting f(0) = 0 is the common error and shifts the whole sequence. Sanity-check with f(2): the recurrence gives f(1) + f(0) = 2, matching the two real routes (1+1, or 2). Naive recursion from these bases is correct but recomputes subproblems and is O(2^n) — memoise it or, better, build upward.

3

Build the table upward, then drop the table

Iterating i from 2 to n and filling dp[i] = dp[i-1] + dp[i-2] is O(n) time and O(n) space with no recursion depth to worry about. But each cell reads only the two before it, so the array is unnecessary: keep two rolling variables and the space falls to O(1). That reduction — noticing how far back the recurrence actually reaches — is the standard finishing move on 1-D DP problems.

04

Solution & live demo

python

▶1class Solution:
▶2    def climbStairs(self, n):
▶3        prev, cur = 1, 1
▶4        for _ in range(2, n + 1):
▶5            prev, cur = cur, prev + cur
▶6        return cur

05

Edge cases

n == 1

The loop never runs and the base value 1 is returned directly.

n == 2

One iteration gives 1 + 1 = 2, which matches enumerating by hand.

n == 0

Returns 1 under the 'one way to do nothing' convention. LeetCode constrains n >= 1, but the base case must still be 1 for the recurrence to produce correct values at n = 2.

Large n

The values grow like Fibonacci, so they exceed 64-bit range around n = 92. Python's unbounded integers handle it; other languages would need big integers or a modulus.

06

Complexity

Time

O(n)

Space

O(1)

Two rolling variables replace the array. Plain recursion without memoisation is O(2^n) and stack-overflows well before it finishes.