Climbing Stairs

Problem Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Examples

Constraints

• 1 ≤ n ≤ 45

Adding Solutions to Subproblems of Smaller Heights

To reach step i, you must make a decision at the preceding steps:

• You could take a single step of size 1 from step i - 1.
• You could take a single step of size 2 from step i - 2.

Therefore, the number of distinct ways to reach step i is the sum of the ways to reach step i - 1 and the ways to reach step i - 2. This recurrence relation, ways(i) = ways(i - 1) + ways(i - 2), matches the Fibonacci sequence.

To find the solution, we can compute values bottom-up. Because we only need the values of the two preceding steps, we can optimize space by storing only two variables instead of a full array.

Solution 1: Dynamic Programming (Bottom-Up, Constant Space)

Iteratively update two variables representing the ways to reach the last two steps.

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int oneStepBefore = 2; // ways to reach step 2
        int twoStepsBefore = 1; // ways to reach step 1
        int allWays = 0;

        for (int i = 3; i <= n; i++) {
            allWays = oneStepBefore + twoStepsBefore;
            // shift states
            twoStepsBefore = oneStepBefore;
            oneStepBefore = allWays;
        }
        return allWays;
    }
}

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

        one_step_before = 2  # ways to reach step 2
        two_steps_before = 1  # ways to reach step 1

        for _ in range(3, n + 1):
            all_ways = one_step_before + two_steps_before
            # shift states
            two_steps_before = one_step_before
            one_step_before = all_ways

        return one_step_before

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;

        int oneStepBefore = 2; // ways to reach step 2
        int twoStepsBefore = 1; // ways to reach step 1
        int allWays = 0;

        for (int i = 3; i <= n; i++) {
            allWays = oneStepBefore + twoStepsBefore;
            // shift states
            twoStepsBefore = oneStepBefore;
            oneStepBefore = allWays;
        }
        return allWays;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We run a single loop up to n.
• Space Complexity: O(1) auxiliary space as we only store state variables.

Where it breaks: If n was larger than 45 (e.g. 100), the number of ways would exceed the bounds of a standard 32-bit signed integer. The constraint of n <= 45 guarantees that the output fits within integer limits.

Common Mistakes

• Using unoptimized recursion. Writing return climbStairs(n-1) + climbStairs(n-2) without memoization runs in O(2^n) time, which will TLE for n = 45.
• Off-by-one errors on initial states. Ensure oneStepBefore and twoStepsBefore map correctly to values for n = 2 and n = 1.
• Creating an array of size n when O(1) space is possible. Storing all intermediate values in an array is acceptable, but optimizing to two variables demonstrates better space awareness.

Frequently Asked Questions

How does this relate to the Fibonacci sequence? The recurrence relationship is identical: F(n) = F(n-1) + F(n-2). The only difference is the starting offset: climbStairs(1) = 1 and climbStairs(2) = 2, which corresponds to F(2) and F(3).

What if we can take 1, 2, or 3 steps? The recurrence becomes ways(i) = ways(i-1) + ways(i-2) + ways(i-3). You would track three state variables instead of two.

What does this problem test in interviews? It tests your ability to identify recursion relationships in problems, optimize recursion with memoization or tabulation, and reduce space from linear to constant.

← All Problems