Climbing Stairs Problem in DSA C - Execution Trace

Concept Flow - Climbing Stairs Problem

Start at step 0

↓

Can climb 1 or 2 steps

↓

Calculate ways to reach step i

↓

ways[i

↓

Repeat until step n

↓

Return ways[n

Start from step 0, at each step calculate ways to reach it by summing ways to previous two steps, repeat until step n.

Execution Sample

DSA C

int climbStairs(int n) {
  int ways[6] = {0};
  ways[0] = 1;
  ways[1] = 1;
  for (int i = 2; i <= n; i++) {
    ways[i] = ways[i-1] + ways[i-2];
  }
  return ways[n];
}

Calculates number of ways to climb n stairs using dynamic programming.

Execution Table

Step	Operation	Index i	ways[i-2]	ways[i-1]	ways[i]	Visual State of ways array
1	Initialize base cases	0	-	-	1	[1, 0, 0, 0, 0, 0]
2	Initialize base cases	1	-	-	1	[1, 1, 0, 0, 0, 0]
3	Calculate ways[2]	2	ways[0]=1	ways[1]=1	2	[1, 1, 2, 0, 0, 0]
4	Calculate ways[3]	3	ways[1]=1	ways[2]=2	3	[1, 1, 2, 3, 0, 0]
5	Calculate ways[4]	4	ways[2]=2	ways[3]=3	5	[1, 1, 2, 3, 5, 0]
6	Calculate ways[5]	5	ways[3]=3	ways[4]=5	8	[1, 1, 2, 3, 5, 8]
7	Return result	n=5	-	-	8	Final ways array: [1, 1, 2, 3, 5, 8]

💡 Reached step n=5, calculation complete, return ways[5]=8

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
i	-	2	3	4	5	5
ways[0]	0	1	1	1	1	1
ways[1]	0	1	1	1	1	1
ways[2]	0	2	2	2	2	2
ways[3]	0	0	3	3	3	3
ways[4]	0	0	0	5	5	5
ways[5]	0	0	0	0	8	8

Key Moments - 3 Insights

Why do we start ways[0] and ways[1] with 1?

ways[0] = 1 means there is 1 way to stand at the bottom without climbing. ways[1] = 1 means only 1 way to reach step 1 (one step). See execution_table rows 1 and 2.

Why do we add ways[i-1] and ways[i-2] to get ways[i]?

Because to reach step i, you can come from step i-1 (one step) or step i-2 (two steps). So total ways is sum of both. See execution_table rows 3 to 6.

What happens if n is 0 or 1?

For n=0 or n=1, the base cases ways[0] and ways[1] already give the answer 1, so loop doesn't run. See variable_tracker for initial values.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is ways[4]?

A 2

B 3

C 5

D 8

💡 Hint

Check the 'ways[i]' column at Step 5 in execution_table.

At which step does ways[3] get its value calculated?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Index i' column and find when i=3 is processed in execution_table.

If ways[0] was initialized to 0 instead of 1, what would be the final ways[5]?

A 5

B 8

C 7

D 0

💡 Hint

Think how ways[2] and subsequent values depend on ways[0], see execution_table Step 3.

Concept Snapshot

Climbing Stairs Problem:
- ways[0] = 1, ways[1] = 1 base cases
- For i >= 2: ways[i] = ways[i-1] + ways[i-2]
- Represents ways to reach step i by 1 or 2 steps
- Return ways[n] as total ways to climb n stairs

Full Transcript

The Climbing Stairs Problem counts how many ways to reach the top of n stairs by climbing 1 or 2 steps at a time. We use an array 'ways' where ways[i] stores the number of ways to reach step i. We start with ways[0] = 1 and ways[1] = 1 as base cases. Then for each step i from 2 to n, ways[i] is calculated as the sum of ways[i-1] and ways[i-2]. This is because you can reach step i either from step i-1 by taking one step or from step i-2 by taking two steps. After filling the array up to ways[n], we return ways[n] as the total number of ways to climb n stairs. The execution table shows each step's calculation and the array state. Key moments clarify why base cases are set and how the sum works. The quiz tests understanding of array values at different steps and the effect of changing base cases.

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 number of steps you skip

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

C. The maximum number of steps you can take at once

D. The minimum number of steps to reach the top

Solution

1. Step 1: Understand the problem statement

   The problem asks for the count of all possible ways to climb to the top using steps of size 1 or 2.

2. Step 2: Identify what is being counted

   We count distinct sequences of 1-step and 2-step moves that sum to n steps.

3. Final Answer:

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

4. Quick Check:

   Counting ways = 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 step size instead of counting ways
• Ignoring the step size options

2. Which of the following is the correct base case initialization for the Climbing Stairs problem in C?

easy

A. int ways[1] = 1; int ways[2] = 2;

B. int ways[0] = 1; int ways[1] = 2;

C. int ways[0] = 0; int ways[1] = 1;

D. int ways[1] = 0; int ways[2] = 1;

Solution

1. Step 1: Identify base cases for climbing stairs

   For 1 step, ways = 1 (only one way). For 2 steps, ways = 2 (1+1 or 2).

2. Step 2: Match base cases with options

   int ways[1] = 1; int ways[2] = 2; correctly sets ways[1] = 1 and ways[2] = 2.

3. Final Answer:

   int ways[1] = 1; int ways[2] = 2; -> Option A

4. Quick Check:

   Base cases: ways[1]=1, ways[2]=2 [OK]

Hint: Remember ways(1)=1 and ways(2)=2 base cases [OK]

Common Mistakes:

• Setting ways[0] incorrectly
• Confusing ways for 1 and 2 steps
• Using zero for ways[1]

3. What is the output of the following C code snippet for n = 4?

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 b;
}

printf("%d", climbStairs(4));

medium

A. 7

B. 6

C. 5

D. 4

Solution

1. Step 1: Trace the loop for n=4

   Initial: a=1, b=2 i=3: c=1+2=3, a=2, b=3 i=4: c=2+3=5, a=3, b=5

2. Step 2: Return value after loop

   Return b=5, which is the number of ways to climb 4 steps.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Ways(4) = 5 [OK]

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

Common Mistakes:

• Returning a instead of b
• Off-by-one errors in loop
• Incorrect initial values

4. Identify the bug in this C function for climbing stairs:

int climbStairs(int n) {
    int ways[n+1];
    ways[1] = 1;
    ways[2] = 2;
    for (int i = 3; i <= n; i++) {
        ways[i] = ways[i-1] + ways[i-2];
    }
    return ways[n];
}

medium

A. Array ways is not initialized for ways[0]

B. No bug, code works correctly

C. Accessing ways[2] before initialization

D. Loop should start from i = 2

Solution

1. Step 1: Check array initialization

   Array ways is declared but ways[0] is not initialized, which may cause undefined behavior if accessed.

2. Step 2: Analyze usage of ways[0]

   Though ways[0] is not used in the loop, some compilers or logic might expect it initialized; best practice is to initialize ways[0] = 0.

3. Final Answer:

   Array ways is not initialized for ways[0] -> Option A

4. Quick Check:

   Uninitialized ways[0] can cause issues [OK]

Hint: Always initialize all array elements before use [OK]

Common Mistakes:

• Ignoring ways[0] initialization
• Assuming no undefined behavior without ways[0]
• Starting loop incorrectly

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 approach is correct?

hard

A. Use ways[i] = ways[i-1] + ways[i-3] with base cases ways[0]=1, ways[1]=1, ways[2]=2

B. Use ways[i] = ways[i-1] * ways[i-2] * ways[i-3] with base cases ways[0]=1, ways[1]=1, ways[2]=2

C. Use ways[i] = ways[i-1] + ways[i-2] with base cases ways[0]=1, ways[1]=1

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

Solution

1. Step 1: Understand step size options

   Since steps can be 1, 2, or 3, ways to reach step i include ways to reach i-1, i-2, and i-3.

2. Step 2: Formulate recurrence and base cases

   ways[i] = ways[i-1] + ways[i-2] + ways[i-3]; base cases: ways[0]=1 (one way to stand still), ways[1]=1, ways[2]=2.

3. Final Answer:

   Use ways[i] = ways[i-1] + ways[i-2] + ways[i-3] with base cases ways[0]=1, ways[1]=1, ways[2]=2 -> Option D

4. Quick Check:

   Sum previous 3 ways for steps 1,2,3 [OK]

Hint: Add ways for all allowed step sizes [OK]

Common Mistakes:

• Multiplying ways instead of adding
• Ignoring the 3-step option
• Using wrong base cases