Problem Description

You need to climb a staircase that has n steps to reach the top. At each step, you have two choices for how to proceed:

• Climb 1 step
• Climb 2 steps

The problem asks you to find the total number of distinct ways to climb from the bottom to the top of the staircase.

For example, if n = 3, there are 3 distinct ways to reach the top:

1. Take 1 step + 1 step + 1 step
2. Take 1 step + 2 steps
3. Take 2 steps + 1 step

This is essentially a dynamic programming problem where each position can be reached from either the previous step (by taking 1 step) or from two steps back (by taking 2 steps). The relationship follows the pattern f[i] = f[i-1] + f[i-2], which is the Fibonacci sequence.

The solution uses two variables a and b to track the number of ways to reach the current and previous positions, updating them iteratively for n iterations. The final value in b represents the total number of distinct ways to climb to the top of the staircase.

Intuition

To understand how to solve this problem, let's think about how we reach any particular step. For any step i, there are only two possible ways to arrive at it:

1. From step i-1 by taking a 1-step climb
2. From step i-2 by taking a 2-step climb

This means the total number of ways to reach step i equals the sum of ways to reach step i-1 plus the ways to reach step i-2. This gives us the recurrence relation: f[i] = f[i-1] + f[i-2].

Starting from the base cases:

• f[0] = 1: There's one way to stay at the ground (do nothing)
• f[1] = 1: There's one way to reach the first step (take one step)

From here, we can build up:

• f[2] = f[1] + f[0] = 1 + 1 = 2
• f[3] = f[2] + f[1] = 2 + 1 = 3
• And so on...

This pattern is actually the Fibonacci sequence! Each value depends only on the two previous values.

Since we only need the previous two values to calculate the current one, we don't need to store all values in an array. We can optimize space by using just two variables (a and b) that slide forward as we compute each new value. The variable b always holds the current value (ways to reach current step), while a holds the previous value. We update them in each iteration: the new a becomes the old b, and the new b becomes a + b (the sum of the previous two values).

Learn more about Memoization, Math and Dynamic Programming patterns.

Solution Approach

The solution implements the dynamic programming approach using space optimization. Here's how the algorithm works:

We use two variables a and b to maintain the number of ways to reach the previous two steps:

• a represents f[i-2] (ways to reach two steps back)
• b represents f[i-1] (ways to reach one step back)

Initially, we set:

• a = 0 (corresponding to f[0] = 0 before the first step)
• b = 1 (corresponding to f[1] = 1 for the base case)

The algorithm iterates n times, and in each iteration:

1. We calculate the new value: new_b = a + b (which represents f[i] = f[i-1] + f[i-2])
2. We update the variables by sliding them forward:
   • a becomes the old b
   • b becomes the new value (a + b)

This is done using Python's tuple assignment: a, b = b, a + b

After n iterations, b contains the value of f[n], which is the total number of distinct ways to climb to the top.

Time Complexity: O(n) - We iterate exactly n times.

Space Complexity: O(1) - We only use two variables regardless of the input size, avoiding the need for an array to store all intermediate results.

This approach elegantly transforms the recursive Fibonacci-like relation into an iterative solution with minimal space usage.

Example Walkthrough

Let's walk through the solution with n = 4 (climbing to the 4th step).

Initial Setup:

• a = 0 (represents ways to reach step -1, conceptually)
• b = 1 (represents ways to reach step 0, the ground)

Iteration 1 (calculating ways to reach step 1):

• Calculate: new_b = a + b = 0 + 1 = 1
• Update: a = 1 (old b), b = 1 (new value)
• This means there's 1 way to reach step 1

Iteration 2 (calculating ways to reach step 2):

• Calculate: new_b = a + b = 1 + 1 = 2
• Update: a = 1 (old b), b = 2 (new value)
• This means there are 2 ways to reach step 2: [1+1] or [2]

Iteration 3 (calculating ways to reach step 3):

• Calculate: new_b = a + b = 1 + 2 = 3
• Update: a = 2 (old b), b = 3 (new value)
• This means there are 3 ways to reach step 3: [1+1+1], [1+2], or [2+1]

Iteration 4 (calculating ways to reach step 4):

• Calculate: new_b = a + b = 2 + 3 = 5
• Update: a = 3 (old b), b = 5 (new value)
• This means there are 5 ways to reach step 4: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], or [2+2]

Final Answer: b = 5

The algorithm correctly computes that there are 5 distinct ways to climb 4 steps. Notice how at each iteration, we only keep track of the last two values (stored in a and b), sliding them forward as we progress through the calculation. This demonstrates the space-efficient nature of the solution while maintaining the Fibonacci-like recurrence relation.

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n) because the algorithm uses a single for loop that iterates exactly n times. Each iteration performs a constant amount of work - just updating two variables a and b with simple arithmetic operations.

The space complexity is O(1) because the algorithm only uses a fixed amount of extra space regardless of the input size n. It maintains only two variables a and b throughout the execution, and these variables don't grow with the input size. The space usage remains constant no matter how large n becomes.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Base Cases

A common mistake is misunderstanding what the initial values represent. Developers often incorrectly set:

• a = 1, b = 1 thinking these represent the first two steps
• Or a = 1, b = 2 thinking these are the answers for n=1 and n=2

Why this happens: The confusion arises from not clearly defining what state each variable represents at the start of the iteration.

Correct approach:

• a = 0 represents the number of ways to reach "step 0" (before the staircase)
• b = 1 represents the number of ways to reach "step 0" (the starting position)
• After the first iteration, we get the answer for n=1
• The loop correctly iterates n times to build up to f[n]

2. Incorrect Loop Count

Another pitfall is running the loop n-1 or n+1 times instead of exactly n times, thinking they need to account for base cases differently.

Example of incorrect code:

# Wrong: loops n-1 times
for i in range(1, n):  
    a, b = b, a + b
return b

Solution: Always loop exactly n times with range(n). The initial values are set up so that after n iterations, you have the correct answer.

3. Misunderstanding the Variable Update Order

Some developers try to update variables separately:

# Wrong: This changes 'a' before using it to calculate new 'b'
for _ in range(n):
    a = b          # Error: loses original 'a' value
    b = a + b      # This becomes b + b instead of old_a + b

Solution: Use simultaneous assignment a, b = b, a + b which evaluates the right side completely before assigning, or use a temporary variable:

for _ in range(n):
    temp = a + b
    a = b
    b = temp

4. Not Handling Edge Cases

Failing to consider when n = 0 or n = 1. While the given solution handles these correctly, some might add unnecessary special case checks:

# Unnecessary complexity:
if n == 0:
    return 1  # or 0? This adds confusion
if n == 1:
    return 1

Solution: The iterative approach naturally handles all cases including n=0 (returns 1, which is correct - there's one way to stay at the ground level) and n=1 (returns 1 after one iteration).