Climbing Stairs Problem in DSA Python

Mental Model

You can reach the top by taking either one step or two steps at a time, so the total ways to reach step n is the sum of ways to reach steps n-1 and n-2.

Analogy: Imagine climbing a staircase where you can hop either 1 or 2 steps at once. To get to the top, you think about how many ways you could have arrived at the step just before or two steps before.

Start: step 0 (ground)
Steps: 1 -> 2 -> 3 -> ... -> n (top)
Ways to reach step n = ways to reach n-1 + ways to reach n-2

Dry Run Walkthrough

Input: number of steps n = 4

Goal: Find how many distinct ways to climb to the 4th step taking 1 or 2 steps at a time

Step 1: Initialize ways to reach step 1 and step 2

ways[1] = 1, ways[2] = 2

Why: Base cases: 1 way to reach step 1 (one step), 2 ways to reach step 2 (1+1 or 2)

Step 2: Calculate ways to reach step 3 as ways[2] + ways[1]

ways[3] = 2 + 1 = 3

Why: Step 3 can be reached from step 2 or step 1

Step 3: Calculate ways to reach step 4 as ways[3] + ways[2]

ways[4] = 3 + 2 = 5

Why: Step 4 can be reached from step 3 or step 2

Result:

ways array: [_, 1, 2, 3, 5]
Answer: 5 ways to climb 4 steps

Annotated Code

DSA Python

def climb_stairs(n: int) -> int:
    if n == 0:
        return 0  # base case: no steps
    if n <= 2:
        return n  # base cases: 1 step or 2 steps
    ways = [0] * (n + 1)  # array to store ways to reach each step
    ways[1], ways[2] = 1, 2  # initialize base cases
    for i in range(3, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]  # sum ways from previous two steps
    return ways[n]

# Driver code
n = 4
print(climb_stairs(n))

if n == 0: return 0

handle base case of zero steps explicitly

if n <= 2: return n

handle base cases directly for 1 or 2 steps

ways = [0] * (n + 1)

create storage for ways to reach each step

ways[1], ways[2] = 1, 2

initialize known ways for first two steps

for i in range(3, n + 1): ways[i] = ways[i - 1] + ways[i - 2]

calculate ways for each step by summing previous two

return ways[n]

return total ways to reach step n

Output

5

Complexity Analysis

Time: O(n) because we compute the number of ways for each step from 3 to n once

Space: O(n) because we store the number of ways for each step in an array

vs Alternative: Compared to a naive recursive approach which has exponential time due to repeated calculations, this dynamic programming approach is efficient and avoids repeated work

Edge Cases

n = 1 (minimum steps)

Returns 1 because there is only one way to climb one step

DSA Python

if n <= 2:
    return n

n = 2 (small steps)

Returns 2 because you can climb two single steps or one double step

DSA Python

if n <= 2:
    return n

n = 0 (no steps)

Returns 0 because the base case `if n == 0: return 0` is triggered

DSA Python

if n == 0:
    return 0

When to Use This Pattern

When a problem asks for the number of ways to reach a point with fixed step sizes, use dynamic programming to build the solution from smaller subproblems.

Common Mistakes

Mistake: Using recursion without memoization causing exponential time
Fix: Use a loop with an array to store intermediate results to avoid repeated calculations

Mistake: Not handling base cases n=1 or n=2 correctly
Fix: Add explicit checks for n <= 2 and return n directly

Summary

Calculates how many distinct ways to climb n steps taking 1 or 2 steps at a time.

Use when counting ways to reach a target with fixed step increments.

The number of ways to reach step n equals the sum of ways to reach steps n-1 and n-2.

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