Climbing Stairs

Count possible ways to climb stairs

Climbing Stairs

Problem Statement

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

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

Examples

Example 1

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top:

1. 1 step + 1 step
2. 2 steps

Example 2

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top:

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints

• 1 ≤ n ≤ 45

Solution

Whenever a problem asks us to count all possible ways to do something, or to find the best among many possibilities, recursion is usually a good place to start.

A General Trick for Solving Recurrence Relation Problems

Here's a handy 3-step approach that works for many problems like this one:

1. Try to represent the problem in terms of an index (even if the problem doesn't directly involve an array).
2. At that index, try every possible action allowed by the problem statement.
3. Sum the results if you're counting the number of ways, or take the minimum/maximum if you're optimizing for the best outcome.

Applying This to Climbing Stairs

For this problem, there are exactly two ways to move from a higher step down toward the bottom: take one step, or take two steps.

• We return 1 in the base case, because every time a path successfully reaches the bottom (step 0 or step 1), it counts as one valid way.
• At any other step n, the number of ways to reach the bottom is the sum of the ways from n - 1 steps and the ways from n - 2 steps, since those are the two moves available.

Plain Recursive Solution

var climbStairs = function (n) {

    function recur(n) {

        if (n == 0)
            return 1;
        if (n == 1) return 1;

        let sum = recur(n - 1) + recur(n - 2);

        return sum;
    }

    return recur(n);
};

This works correctly, but it's not optimal — it recalculates the same values many times over, making it slow for larger values of n.

Optimized Solution

Since each step's answer only depends on the results of the previous two steps, we can avoid recursion entirely, and just keep track of those two values as we move forward.

var climbStairs = function (n) {

    let prev1 = 1;
    let prev2 = 0;

    for (let i = 1; i <= n; i++) {

        let sum = prev2 + prev1;

        prev2 = prev1;
        prev1 = sum;
    }

    return prev1;
};

This version runs in O(n) time and uses only O(1) extra space, making it far more efficient than the plain recursive version.