Climbing Stairs Problem in DSA C++ - Deep Dive

Overview - Climbing Stairs Problem

What is it?

The Climbing Stairs Problem asks: given a staircase with a certain number of steps, how many distinct ways can you climb to the top if you can take either one or two steps at a time? It is a simple counting problem that helps understand how to break down problems into smaller parts. This problem is often used to teach basic dynamic programming and recursion.

Why it matters

Without this concept, solving problems that involve counting paths or sequences would be much harder and less efficient. It shows how to avoid repeating work by remembering past results, which saves time and effort. This idea is used in many real-world applications like robot movement, game design, and decision making.

Where it fits

Before this, learners should know basic programming concepts like loops and functions. After this, they can learn more complex dynamic programming problems and optimization techniques.

Mental Model

Core Idea

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

Think of it like...

Imagine climbing a staircase where you can take either one or two steps at a time, like hopping on stones across a river. To reach the current stone, you could have come from one stone behind or two stones behind.

Steps: 0 1 2 3 4 5 ...
Ways:  1 1 2 3 5 8 ...

 0 -> 1 way (stand still)
 1 -> 1 way (one step)
 2 -> 2 ways (1+1 or 2)
 3 -> 3 ways (2+1 or 1+2)
 4 -> 5 ways (3+1 or 2+2)
 5 -> 8 ways (4+1 or 3+2)

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of counting ways to climb stairs with steps of size one or two.

Imagine you have a staircase with n steps. You want to find out how many different ways you can reach the top if you can climb either 1 step or 2 steps at a time. For example, if n=3, you can climb as (1,1,1), (1,2), or (2,1), so 3 ways.

Result

You understand the problem and can list ways for small n by hand.

Understanding the problem clearly is the first step to solving it systematically.

2

Foundation

Counting Ways for Small Steps

Concept: Calculate the number of ways for the first few steps manually to find a pattern.

For n=1, ways=1 (just one step). For n=2, ways=2 (1+1 or 2). For n=3, ways=3 (1+1+1, 1+2, 2+1). For n=4, ways=5. Write these down and observe the numbers.

Result

Sequence: 1, 2, 3, 5 for steps 1 to 4.

Seeing the pattern in small cases helps form a formula for larger n.

3

Intermediate

Formulating the Recurrence Relation

🤔Before reading on: do you think the ways to reach step n depend on ways to reach step n-1 only, or also on step n-2? Commit to your answer.

Concept: Express the problem as a relation where ways to step n depend on previous steps.

To reach step n, you could have come from step n-1 by taking 1 step, or from step n-2 by taking 2 steps. So, ways(n) = ways(n-1) + ways(n-2). This is the key formula.

Result

You have a simple formula to calculate ways for any n using previous results.

Knowing the problem breaks down into smaller subproblems is the heart of dynamic programming.

4

Intermediate

Implementing Recursive Solution

🤔Before reading on: do you think a simple recursive function will be efficient for large n? Commit to your answer.

Concept: Write a function that calls itself to calculate ways using the recurrence relation.

Define a function climb(n): - If n <= 1, return 1 - Else return climb(n-1) + climb(n-2) This directly follows the formula but repeats calculations.

Result

Function returns correct ways but is slow for large n due to repeated work.

Understanding recursion helps but also reveals inefficiency in naive solutions.

5

Intermediate

Optimizing with Memoization

🤔Before reading on: do you think storing results of previous calls will speed up recursion? Commit to your answer.

Concept: Use a memory (cache) to save results of subproblems to avoid repeated work.

Modify climb(n) to store results in an array or map: - If result for n exists, return it - Else compute and store before returning This reduces time from exponential to linear.

Result

Function runs efficiently even for large n by reusing past results.

Knowing how to remember past answers transforms slow recursion into fast dynamic programming.

6

Advanced

Iterative Dynamic Programming Approach

🤔Before reading on: do you think an iterative solution can be simpler and use less memory than recursion? Commit to your answer.

Concept: Use a loop to build up the answer from the bottom instead of recursion.

Create an array dp of size n+1: - dp[0] = 1, dp[1] = 1 - For i from 2 to n: dp[i] = dp[i-1] + dp[i-2] Return dp[n] This avoids function call overhead and is easy to understand.

Result

Efficient and clear solution with O(n) time and space complexity.

Iterative solutions often improve performance and clarity over recursion.

7

Expert

Space Optimization Using Variables

🤔Before reading on: can you calculate ways to step n using only two variables instead of an array? Commit to your answer.

Concept: Since dp[i] depends only on dp[i-1] and dp[i-2], keep track of only two values to save memory.

Initialize two variables a=1 (ways to step 0), b=1 (ways to step 1). For i in 2 to n: c = a + b a = b b = c Return b This uses O(1) space.

Result

Memory usage is minimized while keeping linear time performance.

Recognizing dependencies allows reducing memory, a key optimization in algorithms.

Under the Hood

The problem is a classic example of overlapping subproblems and optimal substructure. Each step's solution depends on the solutions of the two previous steps. The recursive calls form a tree with many repeated calculations. Memoization or bottom-up dynamic programming stores intermediate results to avoid recomputation. The iterative approach uses a simple loop and stores only necessary previous results, making it efficient in time and space.

Why designed this way?

This problem models real-world scenarios where choices depend on recent history, like steps taken. The recurrence relation mirrors the Fibonacci sequence, a well-studied pattern. Early solutions used recursion but were inefficient. Dynamic programming was introduced to optimize by caching results. The design balances simplicity and efficiency, making it a teaching staple.

┌─────────────┐
│ climb(n)    │
│ /        \  │
│ /          \ │
│climb(n-1)  climb(n-2)│
│  |           |       │
│ ...         ...      │
└─────────────┘

Memoization cache stores climb(k) results to avoid recomputation.

Iterative approach:
[dp[0]=1] -> [dp[1]=1] -> [dp[2]=dp[1]+dp[0]] -> ... -> dp[n]

Myth Busters - 4 Common Misconceptions

Quick: Does the number of ways to climb n steps equal 2^n? Commit yes or no.

Common Belief: Some think the number of ways doubles with each step, so ways = 2^n.

Reality: The number of ways follows the Fibonacci pattern, which grows slower than 2^n.

Why it matters: Overestimating ways leads to inefficient algorithms and wrong expectations.

Quick: Is recursion always the best way to solve this problem? Commit yes or no.

Common Belief: Many believe recursion is the simplest and best approach for climbing stairs.

Reality: Naive recursion is inefficient due to repeated calculations; memoization or iteration is better.

Why it matters: Using naive recursion causes slow programs and stack overflow for large n.

Quick: Can you take 3 steps at once in the classic problem? Commit yes or no.

Common Belief: Some assume you can take any number of steps, including 3 or more.

Reality: The classic problem restricts steps to 1 or 2 only; allowing 3 changes the problem.

Why it matters: Misunderstanding step sizes changes the recurrence and solution entirely.

Quick: Does the problem always start counting ways from step 0? Commit yes or no.

Common Belief: People often think counting starts from step 1 only.

Reality: Counting from step 0 with 1 way (standing still) simplifies the formula and base cases.

Why it matters: Wrong base cases cause incorrect results and confusion in implementation.

Expert Zone

1

The problem's recurrence is identical to Fibonacci numbers but shifted by one index, which can confuse indexing in code.

2

Memoization can be implemented with different data structures (arrays, hash maps) depending on constraints and language features.

3

The problem generalizes to variable step sizes, requiring more complex dynamic programming and changing time complexity.

When NOT to use

This approach is not suitable if steps allowed are more than two or variable; then, a generalized dynamic programming or combinatorial approach is needed. Also, if only the count modulo a number is needed for very large n, matrix exponentiation or closed-form formulas are better.

Production Patterns

In real systems, this pattern appears in path counting, robot movement planning, and game level design. Professionals use iterative DP with space optimization for performance and may extend it to more complex step sets or constraints.

Connections

Fibonacci Sequence

The climbing stairs count follows the Fibonacci numbers shifted by one index.

Understanding Fibonacci helps grasp the growth pattern and recurrence relation in climbing stairs.

Dynamic Programming

Climbing stairs is a classic example illustrating dynamic programming principles of overlapping subproblems and optimal substructure.

Mastering this problem builds intuition for solving many optimization and counting problems efficiently.

Combinatorics

Counting ways to climb stairs relates to counting sequences and combinations of steps.

Knowing combinatorial reasoning helps extend the problem to variable step sizes and constraints.

Common Pitfalls

#1 Using naive recursion without caching causes exponential time and stack overflow.

Wrong approach:

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

Correct approach:

int climb(int n, vector& memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = climb(n-1, memo) + climb(n-2, memo);
return memo[n];
}

Root cause:

Not storing intermediate results leads to repeated calculations and inefficiency.

#2 Incorrect base cases cause wrong results, e.g., returning 0 for n=0.

Wrong approach:

int climb(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return climb(n-1) + climb(n-2);
}

Correct approach:

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

Root cause:

Misunderstanding the meaning of step 0 and base cases breaks the recurrence.

#3 Using an array of size n without initializing leads to garbage values and wrong answers.

Wrong approach:

int dp[n];
dp[0] = 1;
// dp[1] not initialized
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

Correct approach:

vector dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

Root cause:

Not initializing all required base cases causes undefined behavior.

Key Takeaways

The Climbing Stairs Problem counts ways to reach the top using steps of size one or two.

Its solution follows a Fibonacci-like recurrence: ways(n) = ways(n-1) + ways(n-2).

Naive recursion is simple but inefficient; memoization or iteration makes it fast.

Space can be optimized by storing only the last two results instead of the whole array.

Understanding this problem builds a foundation for dynamic programming and counting problems.

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