← Back to Python Examples

Climbing Stairs

A disguised Fibonacci problem — teaches recognizing DP patterns and three ways to implement them.

Contents

  1. The Problem
  2. Recognizing the Pattern
  3. Solution 1 — Naive Recursion
  4. Solution 2 — Memoization (Top-Down DP)
  5. Solution 3 — Bottom-Up DP
  6. Solution 4 — O(1) Space

1. The Problem

You are climbing a staircase with n steps. Each time you can take 1 or 2 steps. How many distinct ways can you reach the top?

# n=1 → 1 way:   [1]
# n=2 → 2 ways:  [1+1], [2]
# n=3 → 3 ways:  [1+1+1], [1+2], [2+1]
# n=4 → 5 ways
# n=5 → 8 ways

2. Recognizing the Pattern

To reach step n, you must have come from step n-1 (by taking 1 step) or step n-2 (by taking 2 steps). So:

# ways(n) = ways(n-1) + ways(n-2)
# This is exactly the Fibonacci sequence!
# ways: 1, 2, 3, 5, 8, 13, 21 ...
The power of this problem is that it looks like a counting puzzle but is actually a DP problem in disguise. Recognizing that the answer to step n depends only on steps n-1 and n-2 is the insight.

3. Solution 1 — Naive Recursion (Don't use this)

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

Correct but exponential — O(2ⁿ). climb(40) makes over a billion calls because the same subproblems are recomputed many times.

4. Solution 2 — Memoization (Top-Down DP)

Cache results so each subproblem is computed only once.

from functools import lru_cache

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

print(climb_memo(10))  # 89

Time: O(n). Space: O(n) for the cache.

5. Solution 3 — Bottom-Up DP

Build the answer from the ground up, avoiding recursion entirely.

def climb_dp(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_dp(10))  # 89

6. Solution 4 — O(1) Space

Since each step only depends on the previous two, we only need two variables — not a full array.

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

for i in range(1, 8):
    print(i, climb_stairs(i))
# 1→1, 2→2, 3→3, 4→5, 5→8, 6→13, 7→21
SolutionTimeSpace
Naive recursionO(2ⁿ)O(n) call stack
MemoizationO(n)O(n)
Bottom-up DPO(n)O(n)
Two variablesO(n)O(1)
This progression — naive → memo → bottom-up → space-optimized — is a template for solving almost any DP problem. Interviewers love seeing you articulate each step before jumping to the optimal.