Step combinations to reach the summit

You are standing at the bottom of a staircase with n steps. Each move lets you climb either 1 step or 2 steps. How many distinct ways can you reach the top? This problem, also known as Climbing Stairs on other platforms, is one of the most popular dynamic programming introductions in technical interviews. Google has used it as a warm-up question, and it appears on virtually every Blind 75 and NeetCode study list. If you have never seen dynamic programming before, this is the perfect place to start.

TL;DR

The number of ways to reach step n equals the sum of ways to reach steps n-1 and n-2, because you can arrive at any step from either one step below or two steps below. This is the Fibonacci recurrence. Track two variables (prev1 and prev2) and update them as you iterate from step 3 to n. Return prev2. This runs in O(n) time and O(1) space.

Why This Problem Matters

Climbing Stairs is the gateway to dynamic programming. It teaches you to recognize overlapping subproblems, define a recurrence relation, and optimize from exponential brute force down to linear time. Nearly every DP problem you encounter in interviews, from house robber to coin change to longest increasing subsequence, builds on the same pattern you will learn here.

Understanding the Problem

You are given an integer n representing the total number of steps. At each point, you can climb 1 step or 2 steps. You need to count every distinct sequence of moves that gets you from the ground to step n.

Example 1: n = 2 returns 2 (either [1,1] or [2])

Example 2: n = 3 returns 3 (either [1,1,1], [1,2], or [2,1])

Edge Cases

• n = 1: Only one way, take a single step.
• n = 2: Two ways, take two singles or one double.
• Large n (n = 30): The answer grows fast (1,346,269 ways) but fits comfortably in a 32-bit integer.

The Key Insight

Think about how you arrive at step i. You got there by taking a single step from step i-1, or by taking a double step from step i-2. There are no other options. So the total ways to reach step i is the sum of ways to reach those two previous steps.

This gives us the recurrence:

ways(i) = ways(i-1) + ways(i-2)

If that looks familiar, it should. It is exactly the Fibonacci sequence, shifted by one position. The values for steps 1 through 7 are 1, 2, 3, 5, 8, 13, 21.

Base Cases

Before we can apply the recurrence, we need starting values. Step 1 has exactly 1 way (a single step), and step 2 has exactly 2 ways (two singles or one double). From there, every subsequent step is the sum of the two before it.

For n = 3, we add the ways for steps 1 and 2: 1 + 2 = 3. The three paths are [1,1,1], [1,2], and [2,1].

Walking Through the Algorithm

Let's trace n = 5 step by step. We start with prev1 = 1 (ways for step 1) and prev2 = 2 (ways for step 2), then compute each step from 3 to 5:

At each iteration, current = prev1 + prev2, then we slide the window forward: prev1 takes the old prev2, and prev2 takes the new current. After processing step 5, prev2 = 8, which is our answer.

The Fibonacci Connection

Laying out the values for steps 1 through 7 makes the pattern clear:

Each value is the sum of the two before it. This is the Fibonacci sequence starting from 1, 2 instead of the traditional 0, 1. Recognizing this connection matters because it opens the door to advanced techniques like matrix exponentiation for O(log n) time, though the linear approach is what interviewers expect.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int climbStairs(int n) {
    // Base cases: n=1 has 1 way, n=2 has 2 ways
    if (n <= 2) {
      return n;
    }

    // prev1 = ways(i-2), prev2 = ways(i-1)
    int prev1 = 1;
    int prev2 = 2;

    for (int i = 3; i <= n; i++) {
      int current = prev1 + prev2;
      prev1 = prev2;
      prev2 = current;
    }

    return prev2;
  }
}

The loop runs from 3 to n, computing each step in constant time. When n is 1 or 2, the base case returns immediately without entering the loop.

Why Two Variables Instead of an Array?

A natural first approach is to create an array dp[] where dp[i] holds the number of ways to reach step i. That works and runs in O(n) time, but uses O(n) space. Since each step only depends on the two previous values, we can discard everything older and track just two variables.

This optimization drops space from O(n) to O(1) without changing the time complexity. It is the same idea behind optimizing any Fibonacci-style recurrence.

The Naive Recursive Trap

A common mistake is to implement the recurrence directly as recursion:

// Don't do this - O(2^n) time!
public int climbStairs(int n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

This recalculates the same subproblems over and over. climbStairs(5) calls climbStairs(4) and climbStairs(3), but climbStairs(4) also calls climbStairs(3). The call tree explodes exponentially, reaching O(2^n) time. Adding memoization fixes this to O(n) time and O(n) space, but the iterative two-variable approach is still better for interviews because it uses O(1) space.

Complexity Analysis

Time Complexity: O(n)

The loop iterates from 3 to n, performing one addition and two assignments per step. For n = 30 (the upper constraint), that is 28 iterations, effectively instant.

Space Complexity: O(1)

We use exactly two integer variables (prev1, prev2) plus one temporary (current). No arrays, no recursion stack, no hash maps.

Common Pitfalls

1. Off-by-one on base cases: Returning 1 for both n=1 and n=2 when n=2 should return 2.
2. Forgetting the base case guard: If you skip the n <= 2 check and initialize prev1=1, prev2=2, the loop for n=1 never executes and returns prev2=2 instead of 1.
3. Using naive recursion: Without memoization, the recursive approach times out even for moderate n.
4. Variable swap order: Updating prev1 before using it in the current calculation corrupts the result.

Interview Tips

• Open with the recurrence: "Each step can be reached from one or two steps below, so ways(i) = ways(i-1) + ways(i-2)."
• Mention Fibonacci: Interviewers appreciate the connection and it shows pattern recognition.
• Start with the array approach if needed: It is fine to explain the O(n) space version first, then optimize to O(1) by observing you only need two values.
• Discuss trade-offs: Mention recursive + memoization (O(n) time, O(n) space) versus iterative (O(n) time, O(1) space) versus matrix exponentiation (O(log n) time).
• Test with small values: Manually verify n=1 through n=5 to confirm your code matches expected outputs: 1, 2, 3, 5, 8.

Key Takeaways

• Climbing Stairs reduces to the Fibonacci recurrence: ways(i) = ways(i-1) + ways(i-2), with base cases ways(1) = 1 and ways(2) = 2.
• The iterative two-variable approach achieves O(n) time and O(1) space, making it the optimal interview solution.
• Naive recursion without memoization runs in O(2^n) time due to overlapping subproblems; always optimize.
• This pattern (define recurrence, identify base cases, optimize space) applies to nearly every 1D dynamic programming problem you will see in interviews.
• For follow-ups like "what if you can take 1, 2, or 3 steps?", extend the recurrence to three variables and three base cases using the same technique.

Related Problems

Once you have this pattern down, try these problems that build on the same Fibonacci-style recurrence:

• Street Safe Heist Strategy (House Robber): Same two-variable DP, but with a max() decision at each step.
• Count Paths on a Board (Unique Paths): Extends the recurrence to two dimensions.
• Subarray with Maximum Total (Maximum Subarray): Another single-pass DP with constant space.

These problems and hundreds more are available on Firecode, where you can practice with instant feedback and spaced repetition to build lasting fluency. Whether you are preparing for your first technical interview or targeting a senior role at Google, consistent daily practice on foundational problems like this one makes the difference.

Solutions in Other Languages

Python

class Solution:
    def climb_stairs(self, n: int) -> int:
        if n <= 2:
            return n
        first, second = 1, 2
        for i in range(3, n + 1):
            first, second = second, first + second
        return second

Python's tuple unpacking makes the variable swap clean and atomic, avoiding the need for a temporary variable.

JavaScript

climbStairs(n) {
  if (n <= 2) return n;
  let first = 1;
  let second = 2;
  for (let i = 3; i <= n; i++) {
    let third = first + second;
    first = second;
    second = third;
  }
  return second;
}

TypeScript

climbStairs(n: number): number {
  if (n <= 2) return n;
  let first = 1;
  let second = 2;
  for (let i = 3; i <= n; i++) {
    const third = first + second;
    first = second;
    second = third;
  }
  return second;
}

C++

int climbStairs(int n) {
  if (n <= 2) return n;
  int prev1 = 1;
  int prev2 = 2;
  for (int i = 3; i <= n; ++i) {
    int current = prev1 + prev2;
    prev1 = prev2;
    prev2 = current;
  }
  return prev2;
}

Go

func (s *Solution) ClimbStairs(n int) int {
    if n <= 2 {
        return n
    }
    first, second := 1, 2
    for i := 3; i <= n; i++ {
        first, second = second, first+second
    }
    return second
}

Go supports parallel assignment like Python, keeping the swap concise.

Scala

def climbStairs(n: Int): Int = {
  if (n <= 2) return n
  var first = 1
  var second = 2
  for (_ <- 3 to n) {
    val third = first + second
    first = second
    second = third
  }
  second
}

Kotlin

fun climbStairs(n: Int): Int {
  if (n <= 2) return n
  var prev1 = 1
  var prev2 = 2
  for (i in 3..n) {
    val current = prev1 + prev2
    prev1 = prev2
    prev2 = current
  }
  return prev2
}

Swift

func climbStairs(_ n: Int) -> Int {
    if n <= 2 { return n }
    var prev1 = 1
    var prev2 = 2
    for _ in 3...n {
        let current = prev1 + prev2
        prev1 = prev2
        prev2 = current
    }
    return prev2
}

Rust

pub fn climb_stairs(&self, n: i32) -> i32 {
    if n <= 2 { return n; }
    let mut prev1 = 1;
    let mut prev2 = 2;
    for _ in 3..=n {
        let current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    prev2
}

C#

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev1 = 1;
    int prev2 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    return prev2;
}

Dart

int climbStairs(int n) {
  if (n <= 2) return n;
  int prev1 = 1;
  int prev2 = 2;
  for (int i = 3; i <= n; i++) {
    int current = prev1 + prev2;
    prev1 = prev2;
    prev2 = current;
  }
  return prev2;
}

PHP

public function climbStairs(int $n): int {
    if ($n <= 2) return $n;
    $prev1 = 1;
    $prev2 = 2;
    for ($i = 3; $i <= $n; $i++) {
        $current = $prev1 + $prev2;
        $prev1 = $prev2;
        $prev2 = $current;
    }
    return $prev2;
}

Ruby

def climb_stairs(n)
  return n if n <= 2
  prev1 = 1
  prev2 = 2
  (3..n).each do |i|
    current = prev1 + prev2
    prev1 = prev2
    prev2 = current
  end
  prev2
end