Climbing Stairs Problem in DSA Go

Mental Model

Count how many ways you can reach the top by taking 1 or 2 steps at a time.

Analogy: Imagine climbing a staircase where you can step up either one stair or skip one and step two stairs at once. You want to know all the different ways to reach the top.

Start: 0
Steps: 1 2 3 4 5 ... n
You can move: 0 -> 1 or 0 -> 2
Then from 1 -> 2 or 1 -> 3, and so on.

Dry Run Walkthrough

Input: n = 4 steps

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

Step 1: Calculate ways to reach step 1

ways[0]=1 (base), ways[1]=1 (only one way: single step)

Why: Base cases: from ground to step 1 is only one way

Step 2: Calculate ways to reach step 2

ways[2] = ways[1] + ways[0] = 1 + 1 = 2

Why: You can get to step 2 from step 1 or step 0

Step 3: Calculate ways to reach step 3

ways[3] = ways[2] + ways[1] = 2 + 1 = 3

Why: You can get to step 3 from step 2 or step 1

Step 4: Calculate ways to reach step 4

ways[4] = ways[3] + ways[2] = 3 + 2 = 5

Why: You can get to step 4 from step 3 or step 2

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

// climbStairs returns number of ways to climb n steps
func climbStairs(n int) int {
    if n <= 1 {
        return 1 // base case: 1 way to climb 0 or 1 step
    }
    ways := make([]int, n+1)
    ways[0], ways[1] = 1, 1
    for i := 2; i <= n; i++ {
        ways[i] = ways[i-1] + ways[i-2] // sum ways from previous two steps
    }
    return ways[n]
}

func main() {
    n := 4
    result := climbStairs(n)
    fmt.Printf("Number of ways to climb %d steps: %d\n", n, result)
}

if n <= 1 { return 1 // base case: 1 way to climb 0 or 1 step }

handle base cases where steps are 0 or 1

ways := make([]int, n+1) ways[0], ways[1] = 1, 1

initialize ways array with base values

for i := 2; i <= n; i++ { ways[i] = ways[i-1] + ways[i-2] // sum ways from previous two steps }

calculate ways to reach each step by adding ways to previous two steps

return ways[n]

return total ways to reach nth step

Output

Number of ways to climb 4 steps: 5

Complexity Analysis

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

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 steps)

Returns 1 because standing still counts as one way

DSA Go

if n <= 1 {
        return 1 // base case: 1 way to climb 0 or 1 step
    }

n = 1 (one step)

Returns 1 because only one way to climb one step

DSA Go

if n <= 1 {
        return 1 // base case: 1 way to climb 0 or 1 step
    }

When to Use This Pattern

When a problem asks for counting ways to reach a point with fixed step sizes, use dynamic programming summing previous states because each step depends on a fixed number of previous steps.

Common Mistakes

Mistake: Forgetting base cases and causing index errors or wrong answers
Fix: Always handle n=0 and n=1 explicitly before looping

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

Summary

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

Use when you need to find number of ways to reach a target with fixed step increments.

Each step's ways equals sum of ways to previous two steps, like Fibonacci numbers.

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 total number of distinct ways to reach the top

B. The minimum number of steps to reach the top

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

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 to the top by taking 1 or 2 steps at a time.

2. Step 2: Identify what is being counted

   We count all possible 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 A

4. Quick Check:

   Counting sequences of 1 or 2 steps = total ways [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 allowed
• Counting skipped steps instead of ways

2. Which Go function signature correctly represents a function to solve the Climbing Stairs problem for n steps?

easy

A. func climbStairs(n int) bool

B. func climbStairs(n string) string

C. func climbStairs() int

D. func climbStairs(n int) int

Solution

1. Step 1: Identify input and output types

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

2. Step 2: Match function signature

   Only func climbStairs(n int) int matches input int and output int.

3. Final Answer:

   func climbStairs(n int) int -> Option D

4. Quick Check:

   Input int, output int = correct signature [OK]

Hint: Input and output both must be int for steps and ways [OK]

Common Mistakes:

• Using string instead of int for steps
• Missing input parameter
• Returning bool instead of int

3. What is the output of this Go code for n = 4?

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

fmt.Println(climbStairs(4))

medium

A. 7

B. 6

C. 5

D. 4

Solution

1. Step 1: Trace initial values and loop

   Start with a=1, b=2. Loop i=3 to 4:
   i=3: a=2, b=3
   i=4: a=3, b=5

2. Step 2: Return final value

   Return b=5 after loop ends.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Ways for 4 steps = 5 [OK]

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

Common Mistakes:

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

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

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

medium

A. Return statement should return a instead of b

B. Loop starts at wrong index causing extra iteration

C. Initial values of a and b are incorrect

D. Missing base case for n == 2

Solution

1. Step 1: Analyze loop start and iterations

   Loop starts at i=2 but initial values already cover steps 1 and 2, causing one extra iteration.

2. Step 2: Correct loop start

   Loop should start at i=3 to avoid counting extra ways.

3. Final Answer:

   Loop starts at wrong index causing extra iteration -> Option B

4. Quick Check:

   Loop index off by one causes wrong count [OK]

Hint: Start loop at 3 when initial values cover steps 1 and 2 [OK]

Common Mistakes:

• Starting loop at 2 instead of 3
• Changing initial values incorrectly
• Returning wrong variable

5. You want to find the number of ways to climb 10 steps but can take 1, 2, or 3 steps at a time. How would you modify the climbing stairs approach?

hard

A. Use dynamic programming with dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

B. Use the same formula dp[i] = dp[i-1] + dp[i-2]

C. Only count ways taking 3 steps at a time

D. Multiply the number of ways for 1 and 2 steps

Solution

1. Step 1: Understand the new step options

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

2. Step 2: Formulate recurrence relation

   Number of ways dp[i] = dp[i-1] + dp[i-2] + dp[i-3] to include all possibilities.

3. Final Answer:

   Use dynamic programming with dp[i] = dp[i-1] + dp[i-2] + dp[i-3] -> Option A

4. Quick Check:

   Include all step sizes in sum for dp [OK]

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

Common Mistakes:

• Using old formula for only 1 or 2 steps
• Ignoring 3-step moves
• Multiplying counts instead of adding