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

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно пройти n ступенек.

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

Пример 1:

Ввод: n = 2
Вывод: 2

Объяснение:

Есть два способа добраться до вершины:
1 ступенька + 1 ступенька
2 ступеньки

Пример 2:

Ввод: n = 3
Вывод: 3

Объяснение:

Есть три способа добраться до вершины:
1 + 1 + 1
1 + 2
2 + 1

Ограничения:

• 1 <= n <= 45