Climbing Stairs

Count the ways to climb n steps taking 1 or 2 at a time. The last move to step i came from step i−1 or i−2, so ways(i) = ways(i−1) + ways(i−2). Only the last two values are needed.

Traced input: n = 5 → 8. Original problem: neetcode.io/problems/climbing-stairs

Complexity

Two rolling variables instead of an array.

Key idea

• Every route to step i ends with a 1-step from i−1 or a 2-step from i−2.
• Those two groups don't overlap, so add them.
• It's the Fibonacci sequence shifted by one.

Common mistakes

• Plain recursion without memoisation is O(2ⁿ).
• Off-by-one in the base cases: ways(1) = 1, ways(2) = 2.

Solution

int climbStairs(int n) {
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

def climbStairs(n: int) -> int:
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

int climbStairs(int n) {
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Edge cases

Each one has its own trace in the interactive view.