Climbing Stairs

Approach Summary

dp[i] = dp[i-1] + dp[i-2]. Equivalent to Fibonacci. Space-optimized: track only last two values.

Full Solution & Approach

Let dp[n] be the number of distinct ways to reach step n. You can reach step n only from step n - 1 (one 1-step climb) or from step n - 2 (one 2-step climb), so dp[n] = dp[n-1] + dp[n-2]. This is exactly the Fibonacci sequence with base cases dp[1] = 1 and dp[2] = 2 (equivalently dp[0] = 1, dp[1] = 1). The recurrence only ever needs the previous two values, so collapse the full array into two rolling variables instead of storing dp[1..n]. Iterate from 2 to n, updating so that b becomes a + b and a becomes the old b. The answer is b after the loop. This is the canonical space-optimized 1D DP example — recognizing the Fibonacci structure is the entire insight, and the same skeleton solves House Robber and Tribonacci.

One loop of n iterations with O(1) work each — O(n) time. Two rolling variables — O(1) extra space versus O(n) for the naive dp array.

Solution Code

Solution

def climb_stairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

function climbStairs(n) {
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

public int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return b;
}

int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Edge Cases to Watch

n = 1 → 1 way
n = 2 → 2 ways (1+1, 2)
Large n — the answer grows like Fibonacci; use the iterative form to avoid recursion depth limits

How to Recognize This Pattern

Count ways to reach nth step
Fibonacci-like recurrence

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)