The shape of the problem

You can climb 1 or 2 stairs at a time. How many distinct ways can you reach step n?

Brute force first

Recurse `f(n) = f(n-1) + f(n-2)` without memoization. Exponential because it recomputes `f(k)` over and over.

Trace it on n=5

a=1 b=2                    (f(1)=1, f(2)=2)
i=3 c=a+b=3  → a=2 b=3
i=4 c=a+b=5  → a=3 b=5
i=5 c=a+b=8  → a=5 b=8
return b=8

After computing step i, `a` holds `f(i-1)` and `b` holds `f(i)`. Everything earlier than a has been discarded because it is no longer reachable in one more step.

Shape of the loop

if n <= 2: return n
a, b = 1, 2
for i in 3..n:
  a, b = b, a + b
return b

Pseudocode only — the full worked solution lives in the Solution tab.