Climbing Stairs — InterviewPrepKit

Solving tips

Split on the last move: you reached step n from n-1 (a 1-step) or n-2 (a 2-step), giving f(n) = f(n-1) + f(n-2) - it's Fibonacci.
Use base cases f(0)=f(1)=1 (or f(1)=1, f(2)=2); a common slip is seeding f(2)=3.
Compute bottom-up with two rolling variables for O(n) time, O(1) space; naive recursion is O(2^n) and crawls near n=45.
Double-check n=1: with both variables seeded to 1 the loop is skipped and the correct 1 is returned.

Problem

A staircase has n steps. Starting from the ground, each move you may climb either 1 step or 2 steps. Count the number of distinct sequences of moves that land you exactly on the top step.

Two ways are different if at any point the size of the step taken differs.

Examples

n = 2 → 2 — either 1 + 1 or 2.
n = 3 → 3 — 1+1+1, 1+2, or 2+1.
n = 5 → 8 — the count follows the Fibonacci sequence.

Constraints

1 <= n <= 45

The tiny upper bound (45) means even an O(n) scan is instant; the point of the problem is to recognize the recurrence rather than to survive a large n. (The naive branching recursion, however, is O(2^n) and already crawls near n = 45.)

Think about it first

Hint 1

Focus on the *last* move that put you on step `n`. It was either a single step from `n-1` or a double step from `n-2`. Every full path ends with exactly one of those two moves.

Hint 2

So the number of ways to reach step `n` is the number of ways to reach `n-1` plus the number of ways to reach `n-2` — the two groups of paths are disjoint and together cover everything. What classic sequence is `f(n) = f(n-1) + f(n-2)`?

Hint 3

It's Fibonacci with base cases `f(1) = 1`, `f(2) = 2`. Compute it bottom-up keeping only the last two values, so no array and no recursion stack are needed — `O(n)` time, `O(1)` space.

TL;DR

The answer is the Fibonacci number f(n) with f(1)=1, f(2)=2; compute it bottom-up with two rolling variables — O(n) time, O(1) space.

The recurrence

Let f(k) be the number of distinct ways to reach step k. The final move onto step k is either a 1-step from k-1 or a 2-step from k-2, and those path sets are disjoint, so:

f(k) = f(k-1) + f(k-2)
f(0) = 1        # one way to "stand at the ground": do nothing
f(1) = 1

Approach 1 — Brute-force recursion

Directly translate the recurrence. Each call branches into two.

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

Complexity: O(2^n) time (the call tree is itself a Fibonacci tree), O(n) stack space.

Why the constraints kill it: at n = 45 this makes on the order of 2·10^9 calls — seconds to minutes — because the same subproblems (ways(k) for each k) are recomputed exponentially many times.

Approach 2 — Top-down memoization

The insight: there are only n distinct subproblems, ways(0) … ways(n). Cache each the first time it is computed and every later request is O(1).

from functools import cache

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def ways(k: int) -> int:
            if k <= 1:
                return 1
            return ways(k - 1) + ways(k - 2)
        return ways(n)

Walkthrough (n = 5): ways(5) needs ways(4)+ways(3). ways(4) computes ways(3)+ways(2); when ways(5) later asks for ways(3) it is already cached. Filled values are ways(2)=2, ways(3)=3, ways(4)=5, ways(5)=8 → 8.

Complexity: O(n) time (each ways(k) bodies runs once), O(n) space for cache + stack.

Approach 3 — Bottom-up tabulation

The insight: compute the subproblems in increasing order of k so every dependency is ready before it is needed — no recursion, no cache lookups.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for k in range(2, n + 1):
            dp[k] = dp[k - 1] + dp[k - 2]
        return dp[n]

Complexity: O(n) time, O(n) space for the table.

Approach 4 — Space-optimized (rolling variables)

The insight: dp[k] only ever reads dp[k-1] and dp[k-2]. Keep just those two numbers and slide them forward; the full array is unnecessary.

class Solution:
    def climbStairs(self, n: int) -> int:
        prev, curr = 1, 1                 # f(0), f(1)
        for _ in range(2, n + 1):
            prev, curr = curr, prev + curr
        return curr

Walkthrough (n = 5): start (prev, curr) = (1, 1). Iterations: (1,2) → (2,3) → (3,5) → (5,8). Return curr = 8.

Complexity: O(n) time, O(1) space — the optimal version.

Common pitfalls

Base cases off by one. f(1) is 1, not 2. A common slip is seeding f(2) = 3; keep f(0) = f(1) = 1 and let the loop derive the rest.
Returning curr when n = 1. With the two-variable version above, n = 1 skips the loop and returns the initial curr = 1, which is correct — but only because both variables were seeded to 1. Double-check the tiny cases.
Using plain recursion under a tight limit. Correct but exponential; always add memoization or go bottom-up.

Pattern takeaway

This is the “hello world” of 1-D DP: define f(k) over a single index, split on the last decision (which step size finished the path), and you get a linear recurrence. Whenever the answer at n decomposes into a fixed set of smaller indices, cache those subproblems — and if each state reads only a constant-width window behind it, collapse the table to a handful of rolling variables for O(1) space.