climb_stairs: число способов подняться шагами 1 и 2

Напишите функцию climb_stairs(n: int) -> int.

Вход. Целое неотрицательное n — количество ступеней. Гарантируется n >= 0.

Выход. Количество различных способов подняться на n ступеней, если за один шаг можно шагнуть на 1 или на 2 ступени. Способы, отличающиеся порядком шагов, считаются разными: 1 + 2 и 2 + 1 — это два разных способа.

Поведение на краевых входах.

• n = 0 — ровно один способ (не делать ни одного шага), вернуть 1.
• n = 1 — вернуть 1.
• n = 2 — вернуть 2.

Требование к производительности. Функция должна отрабатывать мгновенно при n = 500, поэтому наивная рекурсия без кэша не подходит.

def climb_stairs(n: int) -> int:
    # ваш код
    pass