Climbing Stairs

Try every climb

From each position, branch into a 1-step move and a 2-step move. Reaching exactly zero remaining steps completes one route; passing the top completes none.

def climb_stairs(n: int) -> int:
    def count_routes(remaining: int) -> int:
        if remaining == 0:
            return 1
        if remaining < 0:
            return 0
        return count_routes(remaining - 1) + count_routes(remaining - 2)
 
    return count_routes(n)

The recursion redraws the same smaller climb many times. For example, routes from step 10 are counted once through the step-11 branch and again through the step-12 branch.

Time O(2ⁿ). Space O(n) for the deepest chain of recursive calls.

Rolling Fibonacci DP

Dynamic programming (DP) means solving reusable smaller subproblems once. Here are the three pieces of the DP:

• State: ways[i] is the number of routes that land exactly on step i.
• Transition: ways[i] = ways[i - 1] + ways[i - 2], because the final move has length 1 or 2.
• Base case: ways[0] = 1 and ways[1] = 1. The empty route is the one way to remain at step 0.

That is the Fibonacci recurrence, the rule that each new count is the sum of the previous two. A full array works, but the transition reads only two older values. Rolling variables are a fixed set of variables that replace entries which are no longer needed.

def climb_stairs(n: int) -> int:
    two_steps_back = 1  # ways[0]
    one_step_back = 1   # ways[1]
 
    for _ in range(2, n + 1):
        current = one_step_back + two_steps_back
        two_steps_back = one_step_back
        one_step_back = current
 
    return one_step_back

After each loop, the two variables hold the counts for the two steps immediately behind the next one. That invariant makes the discarded history irrelevant.

Time O(n). Space O(1).