Climbing Stairs Problem in DSA Python - Execution Trace

Concept Flow - Climbing Stairs Problem

Start at step 0

↓

Check if current step == target

Yes↓

Return 1 way

No↓

Calculate ways from step+1

↓

Calculate ways from step+2

↓

Sum ways from step+1 and step+2

↓

Return total ways

↓

Repeat until step == target

Start from step 0, recursively count ways to reach the top by taking 1 or 2 steps until reaching the target step.

Execution Sample

DSA Python

def climb_stairs(n):
    if n <= 1:
        return 1
    return climb_stairs(n-1) + climb_stairs(n-2)

print(climb_stairs(4))

Calculates number of ways to climb 4 stairs by taking 1 or 2 steps at a time.

Execution Table

Step	Operation	Current n	Recursive Calls	Return Value	Visual State
1	Call climb_stairs(4)	4	climb_stairs(3), climb_stairs(2)		Start at n=4
2	Call climb_stairs(3)	3	climb_stairs(2), climb_stairs(1)		Going deeper n=3
3	Call climb_stairs(2)	2	climb_stairs(1), climb_stairs(0)		Going deeper n=2
4	Call climb_stairs(1)	1	Base case	1	Reached base n=1 → return 1
5	Call climb_stairs(0)	0	Base case	1	Reached base n=0 → return 1
6	Return from climb_stairs(2)	2		1 + 1 = 2	Ways for n=2 is 2
7	Call climb_stairs(1)	1	Base case	1	Reached base n=1 → return 1
8	Return from climb_stairs(3)	3		2 + 1 = 3	Ways for n=3 is 3
9	Call climb_stairs(2)	2	climb_stairs(1), climb_stairs(0)		Going deeper n=2 again
10	Call climb_stairs(1)	1	Base case	1	Reached base n=1 → return 1
11	Call climb_stairs(0)	0	Base case	1	Reached base n=0 → return 1
12	Return from climb_stairs(2)	2		1 + 1 = 2	Ways for n=2 is 2 again
13	Return from climb_stairs(4)	4		3 + 2 = 5	Ways for n=4 is 5
14	End				All recursive calls complete

💡 All recursive calls resolved; total ways to climb 4 stairs is 5

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 6	After Step 8	After Step 13	Final
n	4	3	2	2	3	4	4
Return Value			2	2	3	5	5

Key Moments - 3 Insights

Why do we return 1 when n is 0 or 1?

Because at n=0 or n=1, there is exactly one way to stand still or take a single step to finish, as shown in execution_table rows 4 and 5.

Why do we add climb_stairs(n-1) and climb_stairs(n-2)?

Because from step n, you can reach the top by either taking 1 step (n-1) or 2 steps (n-2), so total ways are sum of both, as seen in rows 6, 8, and 13.

Why does climb_stairs(2) get called multiple times?

Because the recursive solution repeats calls without storing results, causing repeated work, visible in rows 3 and 9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of climb_stairs(3) at step 8?

A 5

B 2

C 3

D 1

💡 Hint

Check the 'Return Value' column at step 8 in execution_table

At which step does the condition n <= 1 cause the function to return 1 for the first time?

A Step 4

B Step 6

C Step 2

D Step 10

💡 Hint

Look for base case returns in execution_table rows 4 and 5

If we change the problem to allow steps of size 1, 2, or 3, how would the number of recursive calls change?

A They would decrease

B They would increase

C They would stay the same

D No recursive calls would be needed

💡 Hint

More step sizes mean more recursive calls per step, increasing total calls

Concept Snapshot

Climbing Stairs Problem:
- Count ways to reach step n by 1 or 2 steps
- Base case: 1 way if n <= 1
- Recursive: ways(n) = ways(n-1) + ways(n-2)
- Exponential calls without memoization
- Result for n=4 is 5 ways

Full Transcript

The Climbing Stairs Problem counts how many ways you can climb to the top by taking 1 or 2 steps at a time. Starting from step 0, the function climb_stairs(n) returns 1 if n is 0 or 1, meaning only one way to stand or take a single step. Otherwise, it calls itself recursively for n-1 and n-2 steps and sums their results. The execution table shows each recursive call and return value, with climb_stairs(4) ultimately returning 5. Key points include understanding the base case returns, why recursive calls add, and noticing repeated calls for the same n without memoization. The quiz tests understanding of return values, base cases, and effect of changing step sizes. This problem is a classic example of recursion with overlapping subproblems.

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