Domain 1EasyCORE

Climbing Stairs

The problem asks us to determine the number of distinct ways to climb a staircase with `n` steps, where we can take either 1 or 2 steps at a time. The input is an integer `n`, representing the total number of steps, and the output should be the number of distinct ways to reach the top.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Dynamic Programming

70. Climbing Stairs

Model: qwen2.5-coder:14b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 48.8%


Problem Breakdown

The problem asks us to determine the number of distinct ways to climb a staircase with n steps, where we can take either 1 or 2 steps at a time. The input is an integer n, representing the total number of steps, and the output should be the number of distinct ways to reach the top.

Inputs:

  • An integer n (1 <= n <= 45)

Outputs:

  • An integer representing the number of distinct ways to climb to the top

Implicit Constraints or Edge Cases:

  • If n is 0, there are no steps to climb, so the output should be 0.
  • The constraints limit n to a maximum of 45, which helps in determining the feasibility of different approaches.

Intuition

To solve this problem, we can start by considering a brute-force approach where we explore all possible combinations of 1 and 2 steps. However, this approach would be inefficient due to its exponential time complexity, as it involves generating all permutations of 1s and 2s that sum up to n.

A more efficient approach is to recognize that the problem can be broken down into smaller subproblems. Specifically, the number of ways to reach step n is the sum of the ways to reach step n-1 (by taking a single step) and the ways to reach step n-2 (by taking two steps). This insight leads us to a dynamic programming solution.

Approach

We will use dynamic programming to solve this problem. The idea is to build up the solution iteratively using previously computed results.

  1. Base Cases:

    • If n is 0, return 0.
    • If n is 1, return 1 (only one way: take a single step).
    • If n is 2, return 2 (two ways: two 1-steps or one 2-step).
  2. Dynamic Programming Array:

    • Create an array dp where dp[i] represents the number of ways to reach step i.
    • Initialize dp[0] = 1, dp[1] = 1, and dp[2] = 2.
  3. Iterative Calculation:

    • For each step from 3 to n, calculate dp[i] as the sum of dp[i-1] and dp[i-2].
    • This represents the number of ways to reach step i by either taking a single step from i-1 or two steps from i-2.
  4. Result:

    • The value at dp[n] will be the number of distinct ways to climb to the top.

Complexity Analysis

  • Time Complexity: O(n) because we iterate through each step once.
  • Space Complexity: O(n) due to the storage required for the dp array.

Solution

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

Edge Cases Handled

  • n = 0: The function returns 0 as there are no steps to climb.
  • n = 1: The function returns 1, as the only way is to take a single step.
  • n = 2: The function returns 2, as there are two ways: either two 1-steps or one 2-step.
  • n = 45: The function handles this within the constraints and efficiently computes the result using dynamic programming.