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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Climbing Stairs

Number: 70

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Meta, Bloomberg, Grammarly, Zoho, Accenture, TikTok, IBM, Flipkart, Accolite, Deloitte, Infosys, ByteDance, Apple, Adobe, Yahoo, Nvidia, J.P. Morgan, Uber, Turing, Citadel, Oracle, Swiggy, Yandex, Qualcomm, Bolt, AMD

Problem Description

You are given a staircase with n steps. At each move, you can take either 1 step or 2 steps. The goal is to determine the number of distinct ways to reach the top.

Key Insights

  • The problem can be solved using dynamic programming because the solution for a given step depends on the solutions of the previous two steps.
  • The recurrence relation is: ways[i] = ways[i-1] + ways[i-2].
  • Base cases: when there is 1 step, there is 1 way; when there are 2 steps, there are 2 ways.
  • This is analogous to the Fibonacci sequence, shifting indices accordingly.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (can be optimized to O(1) using constant space)

Solution

We use a dynamic programming approach to build a solution gradually. The idea is that to reach step i, you could have come from step i-1 (taking one step) or from step i-2 (taking two steps). Therefore, the total number of ways to reach step i is the sum of ways to reach step i-1 and i-2. We initialize dp[1] = 1 and dp[2] = 2, and iterate from 3 to n to fill dp[]. Each code solution below uses this approach with comments to explain the logic.

Code Solutions

# Define a function to compute the number of ways to climb stairs.
def climbStairs(n):
    # Base case: if there is only one step, return 1.
    if n == 1:
        return 1
    # Initialize the dp array with n+1 elements.
    dp = [0] * (n + 1)
    # There is 1 way to climb 1 step.
    dp[1] = 1
    # There are 2 ways to climb 2 steps.
    dp[2] = 2
    # Compute the number of ways for each step from 3 to n.
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Sum of ways from the previous two steps.
    return dp[n]

# Example usage:
print(climbStairs(3))  # Output: 3
← Back to All Questions