Given n steps, the machine must count the distinct ways to reach the top when each move covers either 1 step or 2 steps. This is a counting problem, not a path reconstruction: the machine only outputs a number, never the sequences themselves.
The key insight is that the last move determines the answer. To land on step n, the machine must have come from step n-1 via a one-step move, or from step n-2 via a two-step move, and the two sets of paths are disjoint. So ways(n) = ways(n-1) + ways(n-2), which is exactly the Fibonacci recurrence.
The approach runs bottom-up. First, seed the base cases: ways(1) = 1 and ways(2) = 2. Second, iterate from 3 up to n, keeping only the previous two values instead of a full table, because the recurrence only looks back two slots. Third, return the accumulated value. Time is O(n) and space is O(1) since only two variables are carried forward.
The trickiest edge case is n = 1: the loop body never executes, so the machine must return the seeded value directly rather than indexing into a table that was never built. This is exactly why a sliding-window pair (prev1, prev2) is safer than memoization over a full array for small n.
def climbStairs(n):
if n <= 2:
return n
prev1, prev2 = 2, 1
for _ in range(3, n + 1):
prev1, prev2 = prev1 + prev2, prev1
return prev1