A staircase has n steps. Each move takes you up either 1 step or 2 steps. How many different sequences of moves get you exactly to the top?
Implement climb_stairs(n: int) -> int.
climb_stairs(1) # 1 [1]
climb_stairs(4) # 5 [1,1,1,1] [1,1,2] [1,2,1] [2,1,1] [2,2]
Constraints: 1 <= n <= 90. Python ints don't overflow, so return the exact count.
Trying every sequence of moves is exponential; aim for O(n).
Show hint
Think about the last move: it's either a 1 or a 2. How does that relate the count for n to counts for smaller staircases?