Climbing Stairs Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of climbing stairs with 3 steps

What is the output of the following code that calculates the number of ways to climb 3 stairs if you can take 1 or 2 steps at a time?

DSA Python

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(3))

A 3

B 2

C 4

D 5

💡 Hint

Think about how many ways you can reach step 3 by taking 1 or 2 steps.

For 3 steps, you can climb as: (1,1,1), (1,2), (2,1) which totals 3 ways.

❓ Predict Output

intermediate

Number of ways to climb 5 stairs

What will be printed by this code that calculates ways to climb 5 stairs with steps of 1 or 2?

DSA Python

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(5))

A 8

B 5

C 13

D 7

💡 Hint

Use the relation dp[i] = dp[i-1] + dp[i-2] starting from dp[1]=1 and dp[2]=2.

dp[3]=3, dp[4]=5, dp[5]=8. The code returns dp[5] which is 8, but option A is 5, so check carefully.

❓ Predict Output

advanced

Output of recursive climbing stairs with memoization for 4 steps

What is the output of this recursive function with memoization when called with n=4?

DSA Python

def climb_stairs(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        memo[n] = n
        return n
    memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo)
    return memo[n]

print(climb_stairs(4))

A 7

B 3

C 5

D 6

💡 Hint

Remember the base cases and how memoization stores results.

For n=4, ways = ways(3) + ways(2) = 3 + 2 = 5.

🔧 Debug

advanced

Identify the error in climbing stairs code

What error will this code produce when run?

DSA Python

def climb_stairs(n):
    dp = [0] * n
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(3))

A No error, output is 3

B TypeError: unsupported operand type(s)

C NameError: name 'dp' is not defined

D IndexError: list assignment index out of range

💡 Hint

Check the size of the dp list and the indices used.

dp list has size n=3, so indices 0,1,2 are valid. dp[2] = 2 is okay, but dp[3] access in loop causes IndexError.

🚀 Application

expert

Number of ways to climb stairs with 1, 2, or 3 steps

What is the output of this code that calculates ways to climb 4 stairs if you can take 1, 2, or 3 steps at a time?

DSA Python

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

print(climb_stairs(4))

A 6

B 7

C 5

D 4

💡 Hint

Count all ways to reach step 4 using 1, 2, or 3 steps.

Ways to climb 4 steps with 1,2,3 steps are 7: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1).

Practice

1. What does the Climbing Stairs problem ask you to find?
Given n steps, how many distinct ways can you climb to the top if you can take 1 or 2 steps at a time?

easy

A. The total number of steps climbed

B. The maximum number of steps you can climb at once

C. The minimum number of steps to reach the top

D. The number of distinct ways to reach the top

Solution

1. Step 1: Understand the problem statement

   The problem asks for the count of different ways to climb to the top using 1 or 2 steps at a time.

2. Step 2: Identify what is being asked

   We want the total number of distinct sequences of 1-step and 2-step moves that sum to n.

3. Final Answer:

   The number of distinct ways to reach the top -> Option D

4. Quick Check:

   Count ways to climb = number of sequences [OK]

Hint: Count sequences of 1 or 2 steps to reach n [OK]

Common Mistakes:

• Confusing number of ways with minimum steps
• Thinking about maximum steps instead of ways
• Counting total steps instead of sequences

2. Which of the following Python function signatures correctly represents a function to solve the Climbing Stairs problem?

easy

A. def climb_stairs(n: int) -> int:

B. def climb_stairs(n): return str

C. def climb_stairs(n: str) -> int:

D. def climb_stairs() -> int:

Solution

1. Step 1: Check parameter and return types

   The input n is an integer representing steps, and output is an integer count of ways.

2. Step 2: Match function signature

   def climb_stairs(n: int) -> int: correctly uses int input and int output with type hints.

3. Final Answer:

   def climb_stairs(n: int) -> int: -> Option A

4. Quick Check:

   Input int, output int function signature [OK]

Hint: Input is int steps, output is int ways [OK]

Common Mistakes:

• Using string type for input
• Returning string instead of int
• Missing input parameter

3. What is the output of this code?

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

print(climb_stairs(5))

medium

A. 5

B. 8

C. 13

D. 10

Solution

1. Step 1: Trace initial values and base cases

   For n=5, start with a=1, b=2. Loop runs for i=3 to 5.

2. Step 2: Calculate loop iterations

   Iteration 3: a=2, b=3; Iteration 4: a=3, b=5; Iteration 5: a=5, b=8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Ways to climb 5 steps = 8 [OK]

Hint: Use Fibonacci-like addition for steps count [OK]

Common Mistakes:

• Returning n for all inputs
• Off-by-one errors in loop
• Mixing a and b values

4. Find the error in this code snippet for climbing stairs:

def climb_stairs(n: int) -> int:
    if n == 1:
        return 1
    a, b = 1, 2
    for i in range(2, n):
        a = b
        b = a + b
    return b

print(climb_stairs(4))

medium

A. Variables a and b are updated incorrectly

B. Loop range should start from 3

C. Base case for n == 2 is missing

D. Return statement should be 'return a'

Solution

1. Step 1: Analyze variable updates inside loop

   Inside loop, a is set to b, then b = a + b uses updated a, causing wrong sum.

2. Step 2: Correct update order

   We must update both simultaneously like a, b = b, a + b to avoid using updated a prematurely.

3. Final Answer:

   Variables a and b are updated incorrectly -> Option A

4. Quick Check:

   Simultaneous update needed for correct Fibonacci logic [OK]

Hint: Update a,b together to avoid wrong sums [OK]

Common Mistakes:

• Updating variables sequentially causing wrong values
• Wrong loop range causing missed steps
• Missing base cases

5. You want to find the number of ways to climb 10 steps but can take 1, 2, or 3 steps at a time. Which modification to the standard climbing stairs solution is correct?

hard

A. Use dp[i] = dp[i-1] * dp[i-2] * dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

B. Use dp[i] = dp[i-1] + dp[i-2] with base dp[0]=1, dp[1]=1

C. Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

D. Use dp[i] = dp[i-1] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

Solution

1. Step 1: Understand step options and recurrence

   With steps 1, 2, or 3 allowed, ways to reach i = sum of ways to reach i-1, i-2, and i-3.

2. Step 2: Set correct base cases

   dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2 (1+1 or 2 steps).

3. Final Answer:

   Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2 -> Option C

4. Quick Check:

   Sum previous three dp values for 3-step climb [OK]

Hint: Sum ways from last 3 steps for 1-2-3 step climb [OK]

Common Mistakes:

• Multiplying dp values instead of adding
• Using only two previous dp values
• Incorrect base cases