p05 Climbing Stairs — Progressive Hints

One hint. 5-min timer. Retry.

Hint 1 — Decompose by last move

To reach step n, what was your last move? Only two possibilities. Each leads to a sub-problem of the same shape.

Hint 2 — Recurrence

Let f(n) = number of distinct ways to reach step n. The last move was either a 1-step (so the previous state was step n-1) or a 2-step (so the previous state was step n-2). These are disjoint sets of paths.

What does this give you?

Hint 3 — Recognize the pattern

f(n) = f(n-1) + f(n-2) — Fibonacci. You only need to track the last two values, so you don’t need an array.

Hint 4 — Pseudocode

if n <= 2: return n
prev2, prev1 = 1, 2    # f(1), f(2)
for i in 3..n:
    prev2, prev1 = prev1, prev1 + prev2
return prev1

Make sure you handle n == 1 and n == 2 as base cases — the loop doesn’t execute for them, so they need explicit returns.

Hint 5 — The full DP recipe (apply this to EVERY DP problem from now on)

  1. State: f(k) = number of distinct ways to reach step k.
  2. Recurrence: f(k) = f(k-1) + f(k-2) — justified by case-split on the last move.
  3. Base cases: f(1) = 1, f(2) = 2. (Two base cases because the recurrence reaches back 2.)
  4. Order: Bottom-up, smaller k first.
  5. Space: Only last two values referenced → two scalars, O(1) space.

The most common interview mistakes:

  • Plain recursion without memo (O(2^N) — TLE).
  • DP array of size N+1 (works, but signals you didn’t see the compression).
  • Forgetting one base case (off-by-one on n=1 or n=2).
  • Confusing this with “distinct step sets” instead of “distinct sequences” — 1+2 and 2+1 are different here.

Time O(N), Space O(1).