Climbing Stairs Problem in DSA Typescript

Mental Model

You want to find how many ways you can reach the top of stairs by taking 1 or 2 steps at a time.

Analogy: Imagine climbing stairs where you can take either one step or jump two steps at once. Counting all possible ways to reach the top is like counting all different paths you can take.

Start -> [Step 0]
Step 1 -> [Step 1]
Step 2 -> [Step 2]
...
Step n -> [Top]

Dry Run Walkthrough

Input: stairs: 4 steps

Goal: Find how many distinct ways to reach step 4 by taking 1 or 2 steps at a time

Step 1: At step 0, ways to reach = 1 (starting point)

ways[0] = 1

Why: We start at the bottom, so there is exactly one way to be there

Step 2: Calculate ways to reach step 1: ways[1] = ways[0] = 1

ways = [1, 1]

Why: From step 0, only one way to step 1 by taking one step

Step 3: Calculate ways to reach step 2: ways[2] = ways[1] + ways[0] = 1 + 1 = 2

ways = [1, 1, 2]

Why: Step 2 can be reached from step 1 or step 0

Step 4: Calculate ways to reach step 3: ways[3] = ways[2] + ways[1] = 2 + 1 = 3

ways = [1, 1, 2, 3]

Why: Step 3 can be reached from step 2 or step 1

Step 5: Calculate ways to reach step 4: ways[4] = ways[3] + ways[2] = 3 + 2 = 5

ways = [1, 1, 2, 3, 5]

Why: Step 4 can be reached from step 3 or step 2

Result:

ways = [1, 1, 2, 3, 5]
Answer: 5 ways to climb 4 steps

Annotated Code

DSA Typescript

class ClimbingStairs {
  static climbStairs(n: number): number {
    if (n <= 1) return 1
    const ways: number[] = new Array(n + 1).fill(0)
    ways[0] = 1 // base case: 1 way to stand at step 0
    ways[1] = 1 // base case: 1 way to reach step 1
    for (let i = 2; i <= n; i++) {
      ways[i] = ways[i - 1] + ways[i - 2] // sum ways from previous two steps
    }
    return ways[n]
  }
}

// Driver code
const stairs = 4
const result = ClimbingStairs.climbStairs(stairs)
console.log(result)

if (n <= 1) return 1

handle base cases where stairs are 0 or 1

ways[0] = 1 // base case: 1 way to stand at step 0

initialize ways to stand at the bottom

ways[1] = 1 // base case: 1 way to reach step 1

initialize ways to reach first step

for (let i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2] }

calculate ways to reach step i by summing ways to reach previous two steps

return ways[n]

return total ways to reach top step n

Output

5

Complexity Analysis

Time: O(n) because we calculate ways for each step from 2 to n once

Space: O(n) because we store ways for all steps from 0 to n

vs Alternative: Compared to recursive approach without memoization which is exponential, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

n = 0 (no stairs)

Returns 1 because standing at the bottom counts as one way

DSA Typescript

if (n <= 1) return 1

n = 1 (one stair)

Returns 1 because only one step to climb

DSA Typescript

if (n <= 1) return 1

When to Use This Pattern

When you see a problem asking for number of ways to reach a point with fixed step sizes, use dynamic programming to build solutions from smaller steps.

Common Mistakes

Mistake: Not handling base cases n=0 or n=1 correctly, causing wrong answers or errors
Fix: Add explicit checks for n <= 1 returning 1

Mistake: Using recursion without memoization leading to slow exponential time
Fix: Use bottom-up dynamic programming with an array to store intermediate results

Summary

Calculates how many ways to climb n stairs taking 1 or 2 steps at a time.

Use when counting distinct paths with fixed step increments.

The number of ways to reach step n equals sum of ways to reach steps n-1 and n-2.

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