Climbing Stairs

The Climbing Stairs problem is one of the most popular dynamic programming questions in coding interviews. It appears simple—you’re just counting ways to climb a staircase—but it teaches a deep lesson: many problems that look combinatorial at first glance turn out to have elegant overlapping substructure.

This problem is an introduction to dynamic programming, recurrence relations, and the Fibonacci sequence.

Problem

You are climbing a staircase with n steps. Each time you can take either:

• 1 step, or
• 2 steps

Your task:

Return the total number of distinct ways to reach the top.

You start at step 0, and reaching exactly step n counts as one valid way.

Example

Input:

n = 2

Output:

2

Explanation:

You can climb:

• 1 step + 1 step
• 2 steps

Input:

n = 3

Output:

3

The valid ways are:

• 1 + 1 + 1
• 1 + 2
• 2 + 1

Solution

At first, you might try enumerating all combinations of 1 and 2 steps, but that quickly becomes unmanageable as n grows. Instead, notice the structure:

To reach step n:

• You could have come from step n - 1 (taking 1 step), or
• You could have come from step n - 2 (taking 2 steps)

So the total ways to reach n is simply:

ways[n] = ways[n - 1] + ways[n - 2]

This is the Fibonacci recurrence.

Key idea

Define:

• ways[1] = 1
• ways[2] = 2

Then build upward. This is dynamic programming at its simplest: computing a large result using already known smaller results.

Why this works

Each step depends only on the two preceding steps. Once you recognize this pattern:

• You avoid exponential recursion.
• You reduce the problem to an \( O(n) \) loop.
• You use constant memory if you store only the last two results.

This makes the solution fast, clean, and optimal.

Algorithm outline (DP iteration)

1. If \( n \) is 1 or 2, return n.
2. Initialize two variables:
   • prev1 = 1 (ways to reach step 1)
   • prev2 = 2 (ways to reach step 2)
3. For each step from 3 to n:
   • Compute current = prev1 + prev2
   • Update prev1 = prev2
   • Update prev2 = current
4. Return prev2 as the final answer.

Sample implementation (Python)

Alternative solution: memoized recursion

You can write a recursive solution with memoization, but:

• It adds overhead compared to simple iteration.
• It’s conceptually helpful but not necessary in an interview.

Poor solution: plain recursion

Naively recursing on:

f(n) = f(n-1) + f(n-2)

without memoization leads to exponential time—far too slow for large n.

Interview insight

The Climbing Stairs problem is a foundational dynamic programming exercise. Interviewers love it because it reveals:

• Whether you can identify subproblems and overlapping structure
• Whether you recognize Fibonacci-like patterns
• Whether you understand how to convert recursion to DP iteration
• Whether you can optimize to constant space

Once you understand this recurrence pattern, you’ll see it everywhere—tiling problems, jump problems, and path-counting challenges all follow similar logic.