Climbing Stairs

Easy Problem 115 of 151 Java and Python

Problem

You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. In how many distinct ways can you reach the top?

Example 1

Input: n = 2
Output: 2
Why: 1 + 1, or 2.

Example 2

Input: n = 3
Output: 3
Why: 1 + 1 + 1, 1 + 2, or 2 + 1.

Constraints

1 ≤ n ≤ 45

Explanation

Your last move onto step n was either a 1-step from n - 1 or a 2-step from n - 2. So ways(n) = ways(n - 1) + ways(n - 2), with ways(1) = 1 and ways(2) = 2: the Fibonacci numbers.

Plain recursion recomputes the same values exponentially often. Building up from the bottom needs only the last two values.

Approach 1 · Naive

Plain recursion

Time O(2ⁿ)
Space O(n) recursion

Translate the recurrence directly. Correct, but ways(n - 2) is recomputed inside ways(n - 1), and so on, doubling the work at each level.

If n <= 2, return n.
Return ways(n - 1) + ways(n - 2).

Java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

Approach 2 · Optimal

Bottom-up with two variables

Time O(n)
Space O(1)

Walk up from step 1, keeping only the counts for the previous two steps.

Set prev = 1 (ways to reach step 1) and curr = 2 (step 2).
For steps 3 to n: next = prev + curr, then shift prev = curr, curr = next.
Return the count for step n.

Java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int prev = 1;
        int curr = 2;
        for (int step = 3; step <= n; step++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2ⁿ)	O(n) recursion
Optimal Bottom-up with two variables	O(n)	O(1)

Key takeaways

The DP recipe: define the state (ways(i)), find the recurrence from the last decision, set base cases, then remove repeated work.
Memoized recursion (top-down) is the middle step between the two approaches above.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem