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.