We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Climbing Stairs

Difficulty: Easy

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?

Key Insights

  • The problem can be approached using dynamic programming.
  • The number of distinct ways to reach step n can be derived from the sum of ways to reach the two preceding steps: ways(n) = ways(n-1) + ways(n-2).
  • Base cases are ways(1) = 1 and ways(2) = 2.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (if using iterative approach) or O(n) (if using a list to store results)

Solution

The problem can be solved using dynamic programming by maintaining an array to store the number of ways to reach each step. Alternatively, an iterative approach can be used to keep track of only the last two steps, reducing the space complexity. The essence of the solution is to recognize that the number of ways to reach the current step is the sum of the ways to reach the two steps before it.

Code Solutions

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    a, b = 1, 2  # Base cases: ways to reach step 1 and step 2
    for i in range(3, n + 1):
        a, b = b, a + b  # Update for the next step
    return b  # The number of ways to reach step n
← Back to All Questions