Stair Climbing

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

Пример 1:

Ввод: n = 2

Вывод: 2

Объяснение: Чтобы подняться на вершину лестницы из 2 ступеней, вы можете либо дважды подняться на 1 ступень, либо подняться на 2 ступени сразу. Таким образом, существует 2 различных способа подняться на вершину.

Пример 2:

Ввод: n = 3

Вывод: 3

Объяснение: Чтобы подняться на вершину лестницы из 3 ступеней, вы можете трижды подняться на 1 ступень, подняться на 1 ступень, а затем на 2 ступени, или подняться на 2 ступени, а затем на 1 ступень. Таким образом, существует 3 различных способа подняться на вершину.

Пример 3:

Ввод: n = 4

Вывод: 5

Объяснение: Чтобы подняться на вершину лестницы из 4 ступеней, существует 5 вариантов: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Где каждое число представляет собой подъем на 1 или 2 ступени за раз, и порядок имеет значение.