70. Climbing Stairs

Easy

MathDynamic ProgrammingMemoization

Answered: Mar 24, 2026

View on LeetCode

Problem Description

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?

Examples

Example 1

Input: n = 2

Output: 2

Explanation:

There are two ways to climb to the top.

1 step + 1 step
2 steps

Example 2

Input: n = 3

Output: 3

Explanation:

There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints

1 <= n <= 45

💡 Hints (1)

Solutions

Complexity Analysis

Time Complexity:

O (n)

We perform a single loop from 3 to n, executing a constant amount of work per iteration.

Space Complexity:

O (1)

Only two variables (a and b) plus one temporary variable are used, regardless of input size.

This approach recognizes that the number of ways to climb n stairs follows the Fibonacci recurrence: ways(n) = ways(n-1) + ways(n-2), since from step n you could have come from either n-1 or n-2. Starting from the base cases a = 1 (one way to climb 1 stair) and b = 2 (two ways to climb 2 stairs), we iteratively advance the window by saving b into a temporary variable, computing the new b as the sum of the two previous values, and shifting a up. After n - 2 iterations, b holds the answer.

Complexity Analysis

Time Complexity:

O (n)

We loop from 3 to n once, doing $O(1)$ work per step.

Space Complexity:

O (1)

Only two variables are maintained at any time, with no dependency on input size.

This is the same iterative approach as Solution 1, but uses simultaneous assignment (a, b = b, a + b) to advance the two pointers in a single line, eliminating the need for a temporary variable. Starting from a = 1, b = 2, each iteration shifts a to the previous b and b to their sum, so after n - 2 iterations b holds the answer.

Complexity Analysis

Time Complexity:

O (n)

Each unique value from 3 to n is computed exactly once and cached, so there are $O(n)$ total recursive calls.

Space Complexity:

O (n)

The memo dictionary stores up to n entries, and the recursion call stack reaches a depth of n.

This approach uses top-down dynamic programming: a recursive helper climb computes ways(n) by breaking it into ways(n-1) + ways(n-2), but stores each result in a memo dictionary before returning so that any subproblem is only solved once. On subsequent calls with the same n, the cached value is returned immediately, avoiding the exponential blowup of naive recursion.

Complexity Analysis

Time Complexity:

O (n)

The loop runs from index 3 to n, performing $O(1)$ work at each step.

Space Complexity:

O (n)

The dp array stores n + 1 values.

This approach uses bottom-up dynamic programming by allocating an array dp of size n + 1, seeding dp[1] = 1 and dp[2] = 2, then filling each entry from index 3 to n using the recurrence dp[i] = dp[i-1] + dp[i-2]. The answer is simply dp[n] after the loop completes.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative with Temporary Variable	$O(n)$	$O(1)$	$O(1)$ space, makes the swap logic explicit with a temp variable	Requires an extra temporary variable; more verbose than necessary
Iterative - Pythonic Swap	$O(n)$	$O(1)$	Cleanest and most concise; optimal time and space	Simultaneous assignment may be less intuitive in non-Python languages
Top-Down DP (Memoization)	$O(n)$	$O(n)$	Natural recursive structure mirrors the problem definition	$O(n)$ extra space for memo dict and call stack; recursion overhead
Bottom-Up DP	$O(n)$	$O(n)$	Avoids recursion; straightforward DP table approach	Stores all n+1 values unnecessarily when only the last two are needed

The optimal approach for this problem is Solution 2: Iterative - Pythonic Swap, which achieves $O(n)$ time complexity and $O(1)$ space complexity. It delivers the same optimal performance as Solution 1 but in a single, elegant line using simultaneous assignment, making it the most concise and idiomatic implementation.

Solutions

lines
1class Solution:
  def climbStairs(self, n: int) -> int:
      if n <= 2:
          return n
5
      # Initialize the first two values for the number of ways to climb 1 and 2 stairs.
      a, b = 1, 2
8
      # The number of ways to climb n stairs is the sum of the ways to climb (n-1) and (n-2) stairs.
      for _ in range(3, n + 1):
          temp = b
          b = a + b # Update b to the next value in the sequence, which is the sum of the previous two values.
          a = temp # Update a to the previous value of b (before the update), which is stored in temp.
14
      # After the loop, b will contain the number of ways to climb n stairs.
      return b

Complexity Analysis

Time Complexity:

O (n)

We perform a single loop from 3 to n, executing a constant amount of work per iteration.

Space Complexity:

O (1)

Only two variables (a and b) plus one temporary variable are used, regardless of input size.

lines
1class Solution:
  def climbStairs(self, n: int) -> int:
      if n <= 2:
          return n
5
      # Initialize the first two values for the number of ways to climb 1 and 2 stairs.
      a, b = 1, 2
8
      # The number of ways to climb n stairs is the sum of the ways to climb (n-1) and (n-2) stairs.
      for _ in range(3, n + 1):
          # Update a and b to the next values in the sequence.
          a, b = b, a + b
13
      # After the loop, b will contain the number of ways to climb n stairs.
      return b

Complexity Analysis

Time Complexity:

O (n)

We loop from 3 to n once, doing $O(1)$ work per step.

Space Complexity:

O (1)

Only two variables are maintained at any time, with no dependency on input size.

lines
1class Solution:
  def climbStairs(self, n: int) -> int:
      if n <= 2:
          return n
5
      # Use a dictionary to store previously computed results for each number of stairs
      memo = {}
8
      def climb(n):
          # Check if the result for n stairs is already computed and stored in the memo dictionary
          if n in memo:
              return memo[n]
13
          if n <= 2:
              return n
16
          # Compute the number of ways to climb n stairs by summing the results for n-1 and n-2 stairs
          memo[n] = climb(n - 1) + climb(n - 2)
19
          return memo[n]
21
      # Start the recursive computation with n stairs
      return climb(n)

Complexity Analysis

Time Complexity:

O (n)

Each unique value from 3 to n is computed exactly once and cached, so there are $O(n)$ total recursive calls.

Space Complexity:

O (n)

The memo dictionary stores up to n entries, and the recursion call stack reaches a depth of n.

lines
1class Solution:
  def climbStairs(self, n: int) -> int:
      if n <= 2:
          return n
5
      # Create a dp array to store the number of ways to climb to each step
      dp = [0] * (n + 1)
      dp[1] = 1
      dp[2] = 2
10
      # Fill the dp array using the relation: dp[i] = dp[i - 1] + dp[i - 2]
      for i in range(3, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]
14
      # The answer will be in dp[n]
      return dp[n]

Complexity Analysis

Time Complexity:

O (n)

The loop runs from index 3 to n, performing $O(1)$ work at each step.

Space Complexity:

O (n)

The dp array stores n + 1 values.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative with Temporary Variable	$O(n)$	$O(1)$	$O(1)$ space, makes the swap logic explicit with a temp variable	Requires an extra temporary variable; more verbose than necessary
Iterative - Pythonic Swap	$O(n)$	$O(1)$	Cleanest and most concise; optimal time and space	Simultaneous assignment may be less intuitive in non-Python languages
Top-Down DP (Memoization)	$O(n)$	$O(n)$	Natural recursive structure mirrors the problem definition	$O(n)$ extra space for memo dict and call stack; recursion overhead
Bottom-Up DP	$O(n)$	$O(n)$	Avoids recursion; straightforward DP table approach	Stores all n+1 values unnecessarily when only the last two are needed

Problem Description

Examples

Example 1

Example 2

Constraints

💡 Hints (1)

Solutions

Solution 1: Iterative with Temporary Variable

Complexity Analysis

Explanation

Solution 2: Iterative - Pythonic Swap

Complexity Analysis

Explanation

Solution 3: Top-Down DP (Memoization)

Complexity Analysis

Explanation

Solution 4: Bottom-Up DP

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Constraints

💡 Hints (1)

Solutions

Solution 1: Iterative with Temporary Variable

Complexity Analysis

Explanation

Solution 2: Iterative - Pythonic Swap

Complexity Analysis

Explanation

Solution 3: Top-Down DP (Memoization)

Complexity Analysis

Explanation

Solution 4: Bottom-Up DP

Complexity Analysis

Explanation

Conclusion