Climbing Stairs

Count ways to reach step n using moves of one or two steps.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Climbing Stairs: The count for the next step is the sum of the counts for the two preceding positions.

Input and goalCount ways to reach step `n` using moves of one or two steps.

Initialize two rolling totalsFor n = 5, previous = 0 and current = 1 represent the two values needed before the first loop update.

current=ways(0)10?1?2?3?4?5

inputn = 5rollingStateprevious=0, current=1dependencycurrent=ways(0)=1; previous is the pre-loop sentinel 0

Recognize it

The task counts paths to position n, every final move has one of two fixed lengths, and paths ending with different final moves are disjoint.

Keep true

Before each iteration, previous and current are consecutive recurrence values. Parallel assignment shifts current into previous and stores previous + current as the complete count for the next step.

Reuse it

Classify solutions by their final decision: if every state can only arrive from a fixed small set of predecessor states, add those disjoint counts and retain only the dependency horizon.

Pattern: DP with the last two answers.

Simple idea: Every path to the current step comes from one step back or two steps back. This is the Fibonacci rule.

def climb_stairs(step_count: int) -> int:
   previous, current = 0, 1
   for _ in range(step_count):
      previous, current = current, previous + current
   return current

Cost: $O(n)$ time and $O(1)$ space.