Climbing Stairs Problem in DSA C++

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 to the next stair. 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 each step again 1 or 2 steps forward.

Dry Run Walkthrough

Input: stairs: 4

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

Step 1: Calculate ways to reach step 1

ways[0]=1, ways[1]=1, ways[2]=0, ways[3]=0, ways[4]=0

Why: Only one way to reach step 1: single step from 0

Step 2: Calculate ways to reach step 2

ways[0]=1, ways[1]=1, ways[2]=2, ways[3]=0, ways[4]=0

Why: Ways to step 2 = ways to step 1 + ways to step 0 = 1 + 1 = 2

Step 3: Calculate ways to reach step 3

ways[0]=1, ways[1]=1, ways[2]=2, ways[3]=3, ways[4]=0

Why: Ways to step 3 = ways to step 2 + ways to step 1 = 2 + 1 = 3

Step 4: Calculate ways to reach step 4

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

Why: Ways to step 4 = ways to step 3 + ways to step 2 = 3 + 2 = 5

Result:

ways array: 1 -> 1 -> 2 -> 3 -> 5
Answer: 5 ways to climb 4 stairs

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1; // base case: 1 way to stand still or step 1
        vector<int> ways(n + 1, 0);
        ways[0] = 1; // 1 way to stay at step 0
        ways[1] = 1; // 1 way to reach step 1
        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2]; // sum ways from previous two steps
        }
        return ways[n];
    }
};

int main() {
    Solution sol;
    int stairs = 4;
    cout << sol.climbStairs(stairs) << endl;
    return 0;
}

if (n <= 1) return 1; // base case: 1 way to stand still or step 1

handle smallest inputs directly

ways[0] = 1; // 1 way to stay at step 0

initialize ways to stand still at start

ways[1] = 1; // 1 way to reach step 1

initialize ways to reach first step

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

calculate ways to each step by summing ways to previous two steps

return ways[n];

final answer is ways to reach step n

Output

5

Complexity Analysis

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

Space: O(n) because we store ways for all steps up 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 still counts as one way

DSA C++

if (n <= 1) return 1;

n = 1 (one stair)

Returns 1 because only one step to climb

DSA C++

if (n <= 1) return 1;

large n (e.g., 45)

Calculates efficiently without stack overflow or timeout

DSA C++

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

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 results because each step depends on a fixed number of prior steps.

Common Mistakes

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

Mistake: Not handling base cases n=0 or n=1 correctly
Fix: Add explicit base case checks returning 1 for n <= 1

Summary

Counts the number of distinct ways to climb n stairs taking 1 or 2 steps at a time.

Use when you need to count paths or sequences with fixed step increments.

Each step's ways count is the sum of ways to the two previous steps.

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 maximum number of steps you can take at once

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

C. The minimum number of steps to reach the top

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 n steps taking 1 or 2 steps at a time.

2. Step 2: Identify what is being calculated

   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 B

4. Quick Check:

   Count ways to climb = 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 steps instead of counting ways
• Ignoring the step size constraints

2. Which of the following is the correct C++ function signature to solve the Climbing Stairs problem recursively?

easy

A. int climbStairs(int &n);

B. void climbStairs(int n);

C. int climbStairs(int n);

D. int climbStairs();

Solution

1. Step 1: Identify the return type

   The function should return an integer count of ways, so return type is int.

2. Step 2: Check the parameter list

   We need the number of steps n as input, passed by value as int n.

3. Final Answer:

   int climbStairs(int n); -> Option C

4. Quick Check:

   Return type int and parameter int n [OK]

Hint: Function returns int count and takes int n parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing the parameter n
• Passing n by reference unnecessarily

3. What is the output of the following C++ code?

int climbStairs(int n) {
  if (n <= 2) return n;
  return climbStairs(n-1) + climbStairs(n-2);
}

int main() {
  std::cout << climbStairs(4);
  return 0;
}

medium

A. 7

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace climbStairs(4) calls

   climbStairs(4) = climbStairs(3) + climbStairs(2) climbStairs(3) = climbStairs(2) + climbStairs(1) = 2 + 1 = 3 climbStairs(2) = 2

2. Step 2: Calculate final result

   climbStairs(4) = 3 + 2 = 5

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways for 4 steps = 5 [OK]

Hint: Use recursion formula: ways(n) = ways(n-1) + ways(n-2) [OK]

Common Mistakes:

• Returning n instead of sum for n > 2
• Miscounting base cases
• Confusing return values for climbStairs(3)

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

int climbStairs(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return climbStairs(n-1) * climbStairs(n-2);
}

medium

A. Using multiplication instead of addition in recursion

B. Base cases are incorrect

C. Missing return type

D. Function parameter should be passed by reference

Solution

1. Step 1: Check base cases

   Base cases for n=1 and n=2 are correct returning 1 and 2 respectively.

2. Step 2: Analyze recursive return statement

   It uses multiplication (*) instead of addition (+), which is wrong for counting ways.

3. Final Answer:

   Using multiplication instead of addition in recursion -> Option A

4. Quick Check:

   Recursion sums ways, not multiplies [OK]

Hint: Sum ways from previous two steps, don't multiply [OK]

Common Mistakes:

• Multiplying instead of adding recursive calls
• Incorrect base cases for n=1 or n=2
• Passing parameter by reference unnecessarily

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 approach correctly adapts the Climbing Stairs problem?

hard

A. Use dp[n] = dp[n-1] + dp[n-2] + dp[n-3] with base dp[0]=1, dp[1]=1, dp[2]=2

B. Use dp[n] = dp[n-1] * dp[n-2] * dp[n-3] with base dp[0]=0, dp[1]=1, dp[2]=1

C. Use recursion with only dp[n] = dp[n-1] + dp[n-2]

D. Use dp[n] = dp[n-1] + dp[n-3] ignoring dp[n-2]

Solution

1. Step 1: Understand the step options

   Since steps can be 1, 2, or 3, ways to reach step n = sum of ways to reach n-1, n-2, and n-3.

2. Step 2: Define base cases and recurrence

   Base cases: dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2. Recurrence: dp[n] = dp[n-1] + dp[n-2] + dp[n-3].

3. Final Answer:

   Use dp[n] = dp[n-1] + dp[n-2] + dp[n-3] with base dp[0]=1, dp[1]=1, dp[2]=2 -> Option A

4. Quick Check:

   Sum ways from last 3 steps with correct bases [OK]

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

Common Mistakes:

• Multiplying ways instead of adding
• Ignoring dp[n-3] term
• Wrong base cases causing incorrect counts