Подъём по лестнице

Вы поднимаетесь по лестнице. Нужно n шагов, чтобы дойти до вершины. Каждый раз вы можете подняться на 1 или 2 ступени.

Сколькими различными способами можно подняться на вершину?

Сигнатура

def climb_stairs(n: int) -> int:

Примеры

climb_stairs(2) → 2  # (1+1 или 2)
climb_stairs(3) → 3  # (1+1+1, 1+2, 2+1)
climb_stairs(4) → 5

Constraints

- 1 ≤ n ≤ 45