Climbing Stairs

The problem

You climb a staircase of n steps. Each move takes you either 1 step or 2 steps. How many distinct sequences of moves reach the top?

Pattern: optimal substructure → DP

Let $f(n)$ be the answer. The first move is either a 1-step (leaving $f(n-1)$ sequences for the rest) or a 2-step (leaving $f(n-2)$). So:

That's the Fibonacci recurrence shifted by one. The interviewer is less interested in "did you spot Fibonacci" and more interested in "can you derive the recurrence and tabulate it without exploding the recursion."

Naive recursive: exponential

Direct translation of the recurrence. $O({\phi }^n)$ time because each call branches into two — the recursion tree is Fibonacci-shaped. For $n=50$, this takes ~30 seconds; for $n=100$, the heat death of the universe.

def climb_naive(n: int) -> int:
    if n <= 1:
        return 1
    return climb_naive(n - 1) + climb_naive(n - 2)

Memoized: O(n)

Each $f(k)$ is computed once and cached. Memoization is the laziest way to turn an exponential recurrence into a polynomial one.

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_memo(n: int) -> int:
    if n <= 1:
        return 1
    return climb_memo(n - 1) + climb_memo(n - 2)

Optimal: O(1) space iteration

We only need the previous two values, not the whole table. Roll two variables forward.

def climb(n: int) -> int:
    if n <= 1:
        return 1
    a, b = 1, 1                # a = f(0), b = f(1)
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Trace

n = 5

a = 1, b = 1                              # f(0) = 1, f(1) = 1
iter 1:  a, b = 1, 2                      # f(2) = 2
iter 2:  a, b = 2, 3                      # f(3) = 3
iter 3:  a, b = 3, 5                      # f(4) = 5
iter 4:  a, b = 5, 8                      # f(5) = 8

return b = 8

Complexity

• Naive: $O({\phi }^n)$ time, $O(n)$ stack.
• Memoized: $O(n)$ time, $O(n)$ table + stack.
• Iterative: $O(n)$ time, $O(1)$ space.
• Matrix exponentiation: $O(\log n)$ time via fast exponentiation of \begin{psmallmatrix}1 & 1 \\ 1 & 0\end{psmallmatrix}. Overkill for the interview question but the right answer for "what's $f(10^{18})$ mod a prime?"

Variations worth knowing

• k different step sizes: recurrence becomes $f(n)={\sum }_{s\in \text{steps}}f(n-s)$. Same DP, more terms.
• Step cost minimization: instead of counting ways, find the minimum-cost path. Replace sum with min.
• Closed form: Binet's formula $f(n)=({\phi }^{n+1}-{\psi }^{n+1})/\sqrt{5}$ with $\phi =(1+\sqrt{5})/2$, $\psi =(1-\sqrt{5})/2$. Floating-point precision dies past $n\approx 70$; matrix-exp wins for big $n$.