Climbing Stairs

EasyDynamic Programming (1-D & 2-D)Blind 75JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're climbing a staircase with n steps, starting at the bottom. Each move climbs either 1 step or 2 steps. Return the number of distinct ways to land exactly on step n, where two ways differ if their sequences of moves differ, so 1+2 and 2+1 count separately.

Examples

n = 2 returns 2

Either two single steps (1+1) or one double step (2).

n = 3 returns 3

The sequences are 1+1+1, 1+2 and 2+1. Order matters, so 1+2 and 2+1 are different ways.

Constraints

1 <= n <= 45

Hints

Hint 1

Think about the very last move onto the top step. Where could you have been standing just before it?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

The last move onto step n is either a 1-step from step n - 1 or a 2-step from step n - 2, so ways(n) = ways(n - 1) + ways(n - 2), the Fibonacci recurrence. Starting from ways(1) = 1 and ways(2) = 2, build upward while keeping only the last two values in prev2 and prev1, since nothing older is needed again. The loop runs n - 2 times.

Time

O(n)

Space

O(1)

Pitfall

Plain recursion on ways(n - 1) + ways(n - 2) recomputes the same steps again and again and takes O(2^n) time, which is far too slow near n = 45. Build from the bottom up or cache results.

Solutions

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

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1