Skip to content
C Codeloom
DSA

LeetCode Climbing Stairs: Fibonacci in Disguise

Walk through LeetCode 70 Climbing Stairs from brute force recursion to bottom-up DP, with edge cases, complexity analysis, and an interview script.

·5 min read · By Yash Kesharwani
Intermediate 9 min read

What you'll learn

  • ✓Recognize Climbing Stairs as a Fibonacci recurrence
  • ✓Convert top-down recursion into memoized DP
  • ✓Optimize bottom-up DP to O(1) space
  • ✓Reason about overlapping subproblems
  • ✓Explain the solution clearly in an interview

Prerequisites

  • •Comfort with recursion: see /blog/recursion-fundamentals
  • •Basics of DP: see /blog/dynamic-programming-introduction

LeetCode 70, Climbing Stairs, is officially marked Easy, but it is one of the most important warm-up problems for dynamic programming interviews. Almost every DP question you will see later, including House Robber, Coin Change, and Word Break, builds on the recurrence you discover here. Treat this problem as an opportunity to practice the full DP workflow rather than racing to the answer.

The Problem

You are climbing a staircase with n steps. Each move, you can climb either 1 or 2 steps. Return the number of distinct ways you can reach the top.

Example inputs and outputs:

Input:  n = 2
Output: 2
Explanation: 1+1, or 2.

Input:  n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1.

Input:  n = 5
Output: 8

If you write out the answers for n = 1, 2, 3, 4, 5 you get 1, 2, 3, 5, 8. That is the Fibonacci sequence shifted by one position. The recurrence is ways(n) = ways(n - 1) + ways(n - 2), because the last move must be either a single step from n - 1 or a double step from n - 2.

Brute Force

The brute force is the direct translation of the recurrence into recursion.

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

This is correct but exponential. For n = 45, the recursion tree contains billions of calls because every subproblem is recomputed many times. LeetCode will time out around n = 40.

Optimal Solution

The recurrence has overlapping subproblems, so memoize or tabulate. The cleanest version is bottom-up with O(1) space.

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

We only need the last two values, so we keep two scalars and slide them forward. If you prefer an explicit DP table for clarity, this version is also fine:

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

Walk Through an Example

Take n = 5. The table fills in like this:

dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 3
dp[4] = dp[3] + dp[2] = 5
dp[5] = dp[4] + dp[3] = 8

Answer: 8. Mapping this back to the moves, the eight distinct sequences are: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, and 2+2+1.

Edge Cases

  • n = 1: one way. The base case must return 1, not 0.
  • n = 2: two ways. Some implementations forget to handle this and return 1.
  • Large n (constraints typically allow up to n = 45): the answer still fits comfortably in a 64-bit integer. No overflow in Python.
  • Negative or zero n: not in the constraints, but defensive code can return 0.

Complexity Analysis

For the optimal solution:

  • Time: O(n). One pass from 3 to n.
  • Space: O(1) for the two-variable version, O(n) for the table version.

For the naive recursion the time is O(2^n) because each call branches twice and the depth is n. If you need a refresher on these growth rates, see /blog/big-o-notation-explained. With memoization the recursive version drops to O(n) time and O(n) space for the call stack and memo table.

How to Explain It in an Interview

Walk the interviewer through this script:

  1. State the recurrence in plain English. The last step was either a 1 or a 2, so the total count splits into ways(n - 1) + ways(n - 2).
  2. Note that this is Fibonacci, which signals exponential brute force.
  3. Identify overlapping subproblems as the reason DP applies.
  4. Offer both a tabulated version and the O(1) rolling-variable version, and ask which they prefer to see coded.
  5. After coding, dry-run on n = 4 or n = 5 to prove correctness.

The cleanest signal you can send is that you separated recognizing the recurrence from optimizing it. That separation is the core DP skill.

  • House Robber: another pick-or-skip recurrence with two predecessors. See the walkthrough in /blog/dynamic-programming-classic-problems.
  • Min Cost Climbing Stairs (LeetCode 746): same recurrence with a cost array.
  • Fibonacci Number (LeetCode 509): the recurrence in its bare form.
  • Decode Ways (LeetCode 91): same shape, with conditional transitions.
  • Unique Paths (LeetCode 62): 2D version of the same idea.

Wrap up

Climbing Stairs looks trivial but it teaches the full DP workflow in miniature: write the recurrence, observe overlap, memoize or tabulate, then squeeze the state. Once you can do those four moves on autopilot, harder DP problems become variations on a familiar pattern. Use this as your warm-up before any DP interview practice session, and pair it with /blog/dynamic-programming-classic-problems to see the same machinery applied to harder problems.