Climbing Stairs Problem in DSA C++ - Execution Trace

Concept Flow - Climbing Stairs Problem

Start at step 0

↓

Check if current step == target

|Yes↓

Count 1 way

No↓

From current step, jump 1 step

↓

From current step, jump 2 steps

↓

Sum ways from both jumps

↓

Return total ways

Start from step 0, recursively or iteratively count ways to reach the target by jumping 1 or 2 steps, summing all possible paths.

Execution Sample

DSA C++

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

Calculates number of ways to climb n stairs by summing ways to reach previous two steps.

Execution Table

Step	Operation	a (ways to step i-2)	b (ways to step i-1)	c (ways to step i)	Visual State
Start	Initialize a=1, b=2	1	2	-	Ways: step1=1, step2=2, c not set
3	Calculate c = a + b	1	2	3	Ways: step3=3 (1+2)
3	Update a = b	2	2	3	a moves to b's value
3	Update b = c	2	3	3	b moves to c's value
4	Calculate c = a + b	2	3	5	Ways: step4=5 (2+3)
4	Update a = b	3	3	5	a moves to b's value
4	Update b = c	3	5	5	b moves to c's value
5	Calculate c = a + b	3	5	8	Ways: step5=8 (3+5)
5	Update a = b	5	5	8	a moves to b's value
5	Update b = c	5	8	8	b moves to c's value
Exit	Return c as total ways	5	8	8	Total ways to climb 5 steps is 8

💡 Loop ends when i > n; final c holds total ways to climb n steps

Variable Tracker

Variable	Start	After i=3	After i=4	After i=5	Final
a	1	2	3	5	5
b	2	3	5	8	8
c	-	3	5	8	8

Key Moments - 3 Insights

Why do we start with a=1 and b=2?

Because for 1 step, ways=1 and for 2 steps, ways=2; these are base cases used in execution_table rows 'Start' and first iteration.

Why do we add a + b to get c?

Because ways to reach current step equals ways to reach previous step plus ways to reach step before that, as shown in execution_table rows where c = a + b.

Why update a and b after calculating c?

To move the window forward for next iteration, a becomes old b, b becomes new c; see execution_table rows with 'Update a = b' and 'Update b = c'.

Visual Quiz - 3 Questions

Look at the execution_table at step i=4, what is the value of c?

A 3

B 5

C 8

D 2

💡 Hint

Check the row labeled '4' under column 'c (ways to step i)' in execution_table

At which iteration does variable b first become 5?

A i=4

B i=3

C i=5

D Start

💡 Hint

Look at variable_tracker row for b and see when it changes to 5

If we change initial b from 2 to 3, what happens to total ways for n=5?

A Total ways become 9

B Total ways become 10

C Total ways become 11

D Total ways remain 8

💡 Hint

Changing b affects sums c = a + b; trace execution_table sums with b=3 instead of 2

Concept Snapshot

Climbing Stairs Problem:
- Ways to climb n steps = ways(n-1) + ways(n-2)
- Base cases: ways(1)=1, ways(2)=2
- Use iteration with variables a,b,c to track counts
- Update a,b each step: a=b, b=c
- Return c as total ways
- Time: O(n), Space: O(1)

Full Transcript

The Climbing Stairs Problem counts how many ways to reach the top by taking 1 or 2 steps at a time. We start with base cases: 1 way to climb 1 step, 2 ways to climb 2 steps. Then for each step from 3 to n, we calculate ways as sum of ways to previous two steps. Variables a and b hold ways to steps i-2 and i-1, c holds current ways. After calculating c, we update a and b to move forward. Finally, c is returned as total ways. This approach uses simple iteration and constant space.

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 maximum number of steps you can take at once

B. The total number of distinct ways to reach the top

C. The minimum number of steps to reach the top

D. The number of steps you skip

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify what is being calculated

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

3. Final Answer:

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

4. Quick Check:

   Count ways to climb = total distinct sequences [OK]

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

Common Mistakes:

• Confusing number of ways with minimum steps
• Thinking about maximum steps instead of counting ways
• Ignoring the step size constraints

2. Which of the following is the correct C++ function signature to solve the Climbing Stairs problem recursively?

easy

A. int climbStairs(int &n);

B. void climbStairs(int n);

C. int climbStairs(int n);

D. int climbStairs();

Solution

1. Step 1: Identify the return type

   The function should return an integer count of ways, so return type is int.

2. Step 2: Check the parameter list

   We need the number of steps n as input, passed by value as int n.

3. Final Answer:

   int climbStairs(int n); -> Option C

4. Quick Check:

   Return type int and parameter int n [OK]

Hint: Function returns int count and takes int n parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing the parameter n
• Passing n by reference unnecessarily

3. What is the output of the following C++ code?

int climbStairs(int n) {
  if (n <= 2) return n;
  return climbStairs(n-1) + climbStairs(n-2);
}

int main() {
  std::cout << climbStairs(4);
  return 0;
}

medium

A. 7

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace climbStairs(4) calls

   climbStairs(4) = climbStairs(3) + climbStairs(2) climbStairs(3) = climbStairs(2) + climbStairs(1) = 2 + 1 = 3 climbStairs(2) = 2

2. Step 2: Calculate final result

   climbStairs(4) = 3 + 2 = 5

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways for 4 steps = 5 [OK]

Hint: Use recursion formula: ways(n) = ways(n-1) + ways(n-2) [OK]

Common Mistakes:

• Returning n instead of sum for n > 2
• Miscounting base cases
• Confusing return values for climbStairs(3)

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

int climbStairs(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return climbStairs(n-1) * climbStairs(n-2);
}

medium

A. Using multiplication instead of addition in recursion

B. Base cases are incorrect

C. Missing return type

D. Function parameter should be passed by reference

Solution

1. Step 1: Check base cases

   Base cases for n=1 and n=2 are correct returning 1 and 2 respectively.

2. Step 2: Analyze recursive return statement

   It uses multiplication (*) instead of addition (+), which is wrong for counting ways.

3. Final Answer:

   Using multiplication instead of addition in recursion -> Option A

4. Quick Check:

   Recursion sums ways, not multiplies [OK]

Hint: Sum ways from previous two steps, don't multiply [OK]

Common Mistakes:

• Multiplying instead of adding recursive calls
• Incorrect base cases for n=1 or n=2
• Passing parameter by reference unnecessarily

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 approach correctly adapts the Climbing Stairs problem?

hard

A. Use dp[n] = dp[n-1] + dp[n-2] + dp[n-3] with base dp[0]=1, dp[1]=1, dp[2]=2

B. Use dp[n] = dp[n-1] * dp[n-2] * dp[n-3] with base dp[0]=0, dp[1]=1, dp[2]=1

C. Use recursion with only dp[n] = dp[n-1] + dp[n-2]

D. Use dp[n] = dp[n-1] + dp[n-3] ignoring dp[n-2]

Solution

1. Step 1: Understand the step options

   Since steps can be 1, 2, or 3, ways to reach step n = sum of ways to reach n-1, n-2, and n-3.

2. Step 2: Define base cases and recurrence

   Base cases: dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2. Recurrence: dp[n] = dp[n-1] + dp[n-2] + dp[n-3].

3. Final Answer:

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

4. Quick Check:

   Sum ways from last 3 steps with correct bases [OK]

Hint: Add ways from last 3 steps for 1,2,3 step moves [OK]

Common Mistakes:

• Multiplying ways instead of adding
• Ignoring dp[n-3] term
• Wrong base cases causing incorrect counts