Climbing Stairs — The Gateway Problem to 1D Dynamic Programming

Problem Statement#

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints:

• 1 <= n <= 45

Example 1:

Input:  n = 2
Output: 2
Explanation: Two ways: (1 step + 1 step) or (2 steps).

Example 2:

Input:  n = 3
Output: 3
Explanation: Three ways: (1+1+1), (1+2), (2+1).

Example 3:

Input:  n = 5
Output: 8
Explanation: Eight distinct ways to reach step 5.

Why This Problem Matters#

Climbing Stairs (LeetCode 70) is the number-one warm-up dynamic programming question in FAANG phone screens. Amazon, Google, and Meta interviewers use it deliberately because it distills all of DP into its purest form: a choice at each step, overlapping subproblems, and a recurrence that lets you build answers from smaller answers. If you cannot explain the recurrence from first principles, interviewers will notice — even if you arrive at the correct answer.

Beyond the interview table, the Fibonacci recurrence dp[i] = dp[i-1] + dp[i-2] is the seed of an entire problem family: Min Cost Climbing Stairs (LC 746), Decode Ways (LC 91), House Robber (LC 198), and at least a dozen others. Every time the current state depends on the previous one or two states, you are looking at a Fibonacci-variant DP. Climbing Stairs is the moment you learn to recognize that fingerprint instantly.

The problem is also a perfect teaching vehicle for the three canonical DP implementations — recursive brute force, top-down memoization, and bottom-up tabulation — which is exactly why interviewers reach for it when they want to probe how deeply you understand dynamic programming as a framework, not just a collection of tricks.

The Core Insight#

Ask yourself one question: what is the last step you take to arrive at step n?

You either stepped from n-1 (one step) or from n-2 (two steps). There are no other options. Therefore the number of distinct ways to reach step n is exactly the number of ways to reach n-1 plus the number of ways to reach n-2.

This is the recurrence: dp[n] = dp[n-1] + dp[n-2].

Optimal substructure: the answer to n is built from answers to strictly smaller subproblems.

Overlapping subproblems: a naive recursion for dp(n) recomputes dp(n-2) from both dp(n) and dp(n-1), exploding to O(2^n) without memoization.

Base cases: dp(1) = 1 (only way: take one step), dp(2) = 2 (ways: 1+1 or 2).

This is exactly the Fibonacci sequence shifted by one index. dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8, ... These are F(2), F(3), F(4), ... in the standard Fibonacci numbering — a fun pattern to mention in an interview to show mathematical awareness.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential, DO NOT submit)#

The most natural starting point is recursion: to reach step n, you come from n-1 or n-2.

# Python — naive recursion, O(2^n) time — illustrative only
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

// JavaScript — naive recursion
function climbStairs(n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

This recurs over the same subproblems repeatedly. climbStairs(5) calls climbStairs(3) twice, and each of those calls climbStairs(1) and climbStairs(2) again. The call tree doubles at every level, giving O(2^n) time.

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

Cache every subproblem result the first time it is computed. Every subsequent call for the same i returns in O(1).

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def climbStairs(self, n: int) -> int:
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i <= 2:
                return i
            return dp(i - 1) + dp(i - 2)
        return dp(n)

// JavaScript — top-down memoization
var climbStairs = function(n) {
    const memo = new Map();
    function dp(i) {
        if (i <= 2) return i;
        if (memo.has(i)) return memo.get(i);
        const result = dp(i - 1) + dp(i - 2);
        memo.set(i, result);
        return result;
    }
    return dp(n);
};

Each of the n subproblems is solved exactly once. Time is O(n), space is O(n) for the memo table plus O(n) call stack depth.

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

Fill a table from the base cases upward. No recursion, no call stack overhead.

# Python — bottom-up tabulation
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

// JavaScript — bottom-up tabulation
var climbStairs = function(n) {
    if (n <= 2) return n;
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

Optimized Solution#

Since dp[i] only depends on dp[i-1] and dp[i-2], you need only two variables — not the whole array.

# Python — space-optimized, O(n) time, O(1) space
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

// JavaScript — space-optimized, O(n) time, O(1) space
var climbStairs = function(n) {
    if (n <= 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
};

Visual Dry Run#

Tracing n = 5 with the full tabulation table:

Rolling variable trace (a = dp[i-2], b = dp[i-1], computing new b = a + b):

Answer: 8.

Complexity Analysis#

For n up to 45 (per constraints), all O(n) approaches finish in microseconds.

Common Mistakes#

1. Off-by-one in the loop bound. range(3, n) stops at n-1 and never computes dp[n]. Always use range(3, n + 1).

2. Returning the wrong variable when n = 1. If you initialize a=1, b=2 and your guard says if n == 1: return 1, make sure this guard appears before entering the loop. Without it, the loop never runs for n=1 and b=2 is returned instead of 1.

3. Saying "it's Fibonacci" without explaining why. Interviewers want to hear the derivation: "The last step to n was either from n-1 or n-2, so the count is the sum of both." Pattern recognition alone is not enough.

4. Jumping to the closed-form Fibonacci formula. The formula phi^n / sqrt(5) loses floating-point precision for large n and introduces unnecessary complexity. Stick with the O(n) DP unless explicitly asked.

5. Not handling n = 1 before calling lru_cache. If n = 1 and your base case is if i <= 2: return i, that returns 1, which is correct. But if you wrote if i == 0: return 0; if i == 1: return 1; if i == 2: return 2, a call with i=0 returns 0 instead of being unreachable — double-check your base case logic.

6. Confusing this with the counting and the minimum-cost variant. Climbing Stairs counts paths (sum); Min Cost Climbing Stairs minimizes cost (min). The structure is identical but the operation differs.

Interview Tips#

Start with the recurrence, then optimize. Tell your interviewer: "My first observation is that to reach step n, I must come from n-1 or n-2, so dp[n] = dp[n-1] + dp[n-2]." Then show the naive recursion, point out the redundant recomputation, add a memo cache, then drop to bottom-up iteration. This narrative demonstrates DP fluency.

Always state the base cases explicitly. Base cases are the most common source of bugs. Say: "dp[1] = 1 because there is exactly one way to reach step 1. dp[2] = 2 because you can take 1+1 or a single 2-step."

Mention the space optimization proactively. After writing the tabulation solution, say: "Since each step only depends on the previous two, I can compress the table to two variables, reducing space from O(n) to O(1)." This signals senior-level awareness.

Connect it forward. If you have time, mention that this pattern generalizes to k step sizes (dp[i] = sum of last k dp values) and cost variants (multiply by cost[i]). Interviewers at FAANG love when you see the pattern family.

Follow-up Questions#

Q: What if you can take 1, 2, or 3 steps? The recurrence becomes dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Keep three rolling variables instead of two.

Q: What if some steps are broken and you cannot land on them? Set dp[broken_step] = 0. The recurrence for non-broken steps stays the same.

Q: What if step costs are attached and you want minimum cost? That is Min Cost Climbing Stairs (LC 746): dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The sum becomes a min.

Q: Can you solve this in O(log n)? Yes, using matrix exponentiation of the 2x2 Fibonacci matrix. For n up to 45 this is overkill, but it is a valid advanced follow-up.

Q: How many ways are there if you must land on every step? Then the only way is to take exactly n single steps, so the answer is 1.

Q: What if the step sizes are arbitrary, given as a set S? dp[i] = sum(dp[i - s] for s in S if s <= i). This is the full unbounded knapsack counting variant.

Key Takeaways#

• The recurrence dp[n] = dp[n-1] + dp[n-2] comes from one observation: the last move to step n was either a 1-step or a 2-step. Any time there are exactly two ways to arrive at a state and you want the total count, this pattern applies.
• Always derive the recurrence from first principles — do not just say "Fibonacci." Explain the "last step" reasoning.
• Show the three-phase evolution: naive recursion (exponential) → memoization (O(n) time, O(n) space) → tabulation → space-optimized rolling variables (O(n) time, O(1) space).
• Base cases dp[1] = 1 and dp[2] = 2 must be set before the loop; confusing them causes off-by-one bugs on small inputs.
• This Fibonacci-variant DP is the foundation for Min Cost Climbing Stairs, House Robber, Decode Ways, and many other 1D DP problems — recognizing the pattern is a force multiplier in interviews.
• Space optimization to O(1) is always available when dp[i] depends only on a constant number of previous states.