DP: climbing stairs

You're climbing a staircase with n steps. Each move you take either 1 step or 2 steps. How many distinct ways can you reach the top?

The trick to dynamic programming is to notice that a big problem is made of smaller versions of itself. To land on step n, your last move came either from step n - 1 (a single step) or from step n - 2 (a double step). So:

ways(n) == ways(n - 1) + ways(n - 2)

That's the Fibonacci recurrence! Instead of recursing (which recomputes the same values over and over), we build the answers bottom-up and keep only what we need:

a, b = 1, 1
for _ in range(n):
    a, b = b, a + b

Your task

Write climb_stairs(n) that returns the number of distinct ways to climb n steps. There is exactly one way to climb 0 steps (do nothing).

climb_stairs(0)   # 1
climb_stairs(2)   # 2   -> (1+1), (2)
climb_stairs(3)   # 3   -> (1+1+1), (1+2), (2+1)
climb_stairs(5)   # 8

Hint: keep two running totals for "ways to reach the previous step" and "ways to reach the step before that," and roll them forward n times.