Climbing Stairs Problem in DSA Typescript - 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 target by taking 1 or 2 steps, summing all possible paths.

Execution Sample

DSA Typescript

function climbStairs(n: number): number {
  if (n <= 1) return 1;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Counts ways to climb n stairs by summing ways to climb n-1 and n-2 stairs.

Execution Table

Step	Operation	Current n	Recursive Calls	Return Value	Visual State
1	Call climbStairs(3)	3	climbStairs(2), climbStairs(1)	3	Ways(3) = Ways(2) + Ways(1) = 2 + 1 = 3
2	Call climbStairs(2)	2	climbStairs(1), climbStairs(0)	2	Ways(2) = Ways(1) + Ways(0) = 1 + 1 = 2
3	Call climbStairs(1)	1	Base case	1	Ways(1) = 1
4	Call climbStairs(0)	0	Base case	1	Ways(0) = 1
5	Call climbStairs(1)	1	Base case	1	Ways(1) = 1
6	Return final result	3	None	3	Total ways to climb 3 steps = 3

💡 Reached base cases n=0 or n=1, return 1; recursion unwinds summing ways.

Variable Tracker

Variable	Start	After Call 1	After Call 2	After Call 3	Final
n	3	2	1	0	3
Return Value	N/A	2	1	1	3

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 the last step, as shown in execution_table rows 3 and 4.

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

Because from step n, you can reach the top by taking either 1 step or 2 steps, so total ways are sum of ways from n-1 and n-2 steps, as in execution_table row 1.

Why does the recursion stop?

Recursion stops when n reaches 0 or 1, the base cases returning 1, preventing infinite calls, as seen in execution_table rows 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of climbStairs(2) at step 2?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Return Value' column in execution_table row 2.

At which step does the recursion reach the base case for n=0?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the row where n=0 and base case is mentioned in execution_table.

If climbStairs(n-2) was removed from the code, how would the total ways for n=3 change?

A It would become 3

B It would become 2

C It would become 1

D It would become 0

💡 Hint

The code would become `return climbStairs(n-1);`, which recurses down: climbStairs(3) -> climbStairs(2) -> climbStairs(1) -> base case 1, returning 1 up the chain.

Concept Snapshot

Climbing Stairs Problem:
- Count ways to reach step n
- Base cases: ways(0)=1, ways(1)=1
- Recurrence: ways(n) = ways(n-1) + ways(n-2)
- Recursive calls sum ways from previous two steps
- Stops when n <= 1
- Total ways = number of distinct sequences of 1 or 2 steps

Full Transcript

The Climbing Stairs Problem counts how many ways to climb n stairs taking 1 or 2 steps at a time. The code uses recursion: if n is 0 or 1, return 1 because there is only one way to stand or take the last step. Otherwise, return climbStairs(n-1) plus climbStairs(n-2), summing ways from previous steps. The execution table shows calls for n=3, breaking down into calls for n=2 and n=1, then base cases at n=1 and n=0 returning 1. The recursion stops at base cases and sums results on return. Key moments clarify why base cases return 1, why we add two recursive calls, and why recursion stops. The visual quiz tests understanding of return values, base cases, and effect of removing one recursive call.

Practice

1. What does the Climbing Stairs problem ask you to find?
Given n stairs, 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 minimum number of steps to reach the top

C. The number of stairs you skip

D. The total 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 n stairs taking 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 total number of distinct ways to reach the top -> Option D

4. Quick Check:

   Count ways = total distinct 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 allowed
• Counting skipped stairs instead of ways

2. Which of the following TypeScript function signatures correctly represents a function to solve the Climbing Stairs problem?

easy

A. function climbStairs(n: number): number

B. function climbStairs(n: string): string

C. function climbStairs(): void

D. function climbStairs(n: number): void

Solution

1. Step 1: Identify input and output types

   The input is the number of stairs (number), output is the count of ways (number).

2. Step 2: Match function signature

   Only the signature with input number and output number matches the problem requirements.

3. Final Answer:

   function climbStairs(n: number): number -> Option A

4. Quick Check:

   Input and output types match problem [OK]

Hint: Input and output both must be numbers [OK]

Common Mistakes:

• Using string type for number input
• Function returning void instead of number
• No input parameter in function

3. What is the output of the following TypeScript code?

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    let temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}
console.log(climbStairs(4));

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace initial values and loop

   For n=4, start with a=1, b=2. Loop i=3 to 4: - i=3: temp=1+2=3, a=2, b=3 - i=4: temp=2+3=5, a=3, b=5

2. Step 2: Return final value

   Return b=5 as the number of ways to climb 4 stairs.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Ways for 4 stairs = 5 [OK]

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

Common Mistakes:

• Returning a instead of b
• Off-by-one error in loop
• Incorrect initial values for a and b

4. Identify the error in this TypeScript code for climbing stairs:

function climbStairs(n: number): number {
  if (n == 1) return 1;
  let a = 1, b = 2;
  for (let i = 2; i <= n; i++) {
    let temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

medium

A. Initial values of a and b are incorrect

B. Return statement should return a instead of b

C. Loop starts at wrong index causing off-by-one error

D. Missing base case for n == 2

Solution

1. Step 1: Analyze loop start and base cases

   Loop starts at i=2 but initial values assume i=3 start. This causes extra iteration and wrong count.

2. Step 2: Correct loop start

   Loop should start at i=3 to align with initial values a=1, b=2 and base case for n=2.

3. Final Answer:

   Loop starts at wrong index causing off-by-one error -> Option C

4. Quick Check:

   Loop index must match initial conditions [OK]

Hint: Check loop start matches base cases [OK]

Common Mistakes:

• Starting loop at 2 instead of 3
• Ignoring base case for n=2
• Swapping a and b updates

5. You want to find the number of ways to climb 10 stairs but now you can take 1, 2, or 3 steps at a time. Which modification to the climbing stairs logic 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] * dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

C. Use dp[i] = dp[i-1] + dp[i-2] only with base dp[0]=1, dp[1]=1

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 the new step options

   Now steps can be 1, 2, or 3 at a time, so ways to reach i depend on previous 3 states.

2. Step 2: Formulate recurrence relation

   Number of ways to reach step i = sum of ways to reach i-1, i-2, and i-3.

3. Step 3: Set base cases

   dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2 (1+1 or 2 steps).

4. 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 A

5. Quick Check:

   Sum previous 3 states for new step sizes [OK]

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

Common Mistakes:

• Multiplying previous states instead of adding
• Ignoring the 3-step option
• Wrong base cases for dp array