Climbing Stairs: Fibonacci in Disguise

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.

Intuition

The last move to reach step n was either a single step from n - 1 or a double step from n - 2. Those two cases partition all paths, so ways(n) = ways(n - 1) + ways(n - 2). That is Fibonacci, which means naive recursion is exponential because the same subproblems are recomputed exponentially many times. The remedy is to compute each ways(i) exactly once, sweeping bottom up; because only the two previous values matter, two rolling variables suffice.

Explanation with 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.

i      0   1   2   3   4   5
dp[i]  1   1   2   3   5   8
          ^   ^   ^   ^   ^
          |   1+1 1+2 2+3 3+5
          base    |
                dp[2]=dp[1]+dp[0]

Each cell adds the two before it; rolling vars suffice for O(1) space.

Code

The cleanest version is bottom-up with O(1) space using two rolling variables.

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

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

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. 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.

Related Problems

• House Robber: another pick-or-skip recurrence with two predecessors.
• Min Cost Climbing Stairs: same recurrence with a cost array.
• Fibonacci Number: the recurrence in its bare form.
• Decode Ways: same shape, with conditional transitions.
• Unique Paths: 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.