💬 Discord
Sign In
NeetCode #657LC-70Easy1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#657 · #70 · Climbing Stairs(爬楼梯)

📌 Problem Statement & Constraints

You are climbing a staircase with n steps. Each move you may climb either 1 or 2 steps. Return the number of distinct ways to reach the top. Constraints: 1 <= n <= 45, so the answer fits in a 32-bit integer.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the number of ways to reach step i.
  2. The last move is either a single step from i - 1 or a double step from i - 2, so dp[i] = dp[i - 1] + dp[i - 2].
  3. The base cases are dp[0] = 1 (one way to stand still) and dp[1] = 1; this is the Fibonacci sequence shifted by one index.
  4. Only the two previous values are ever needed, so two rolling variables reduce the space to O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2            # ways to reach step 1 and step 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass over the steps (O(1) with the rolling variables).
💾 Space Complexity
O(1): two scalars; an O(n) array also works but is unnecessary.

⚠️ Interview Pitfalls & Follow-ups

  • Trying a closed-form combinatorial sum: the recurrence is the clean formulation; summing over the count of double steps invites arithmetic mistakes.
  • Off-by-one in the base cases: n = 1 is 1 and n = 2 is 2; an array indexed by dp[i] needs size n + 1 with dp[0] = 1.
  • Looping to n - 1 instead of n: the final answer is the value at step n, so the loop bound must be inclusive.
  • Confusing this with problem 746: here every stair costs exactly one move, whereas 746 attaches a different cost to each stair.