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.
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.
Fibonacci wearing a different hat: the ways to reach step n are the ways to reach n-1 plus the ways to reach n-2, because the last move was either one step or two. Since only the last two values matter, two variables replace the whole array.
Approach
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.
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.
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.
Solution & live demo
Common pitfalls
Recursing without memoisation
return self.climbStairs(n-1) + self.climbStairs(n-2)
for _ in range(2, n + 1):
prev, cur = cur, prev + curThe naive recursion recomputes the same subproblems exponentially — around 2^n calls, which stalls well before n = 45. Iterating forward computes each value once.
Seeding the base cases wrong
prev, cur = 0, 1
prev, cur = 1, 1
There is exactly one way to stand at step 0 (do nothing) and one way to reach step 1. Starting from 0 shifts the sequence and returns the answer for n-1.
Assigning the two variables in sequence
prev = cur cur = prev + cur
prev, cur = cur, prev + cur
The first line destroys the old prev before the second line reads it, so cur becomes 2 * cur and the sequence turns into powers of two. Simultaneous assignment reads both right-hand values before writing either.
Edge cases
The loop never runs and the base value 1 is returned directly.
One iteration gives 1 + 1 = 2, which matches enumerating by hand.
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.
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.