Лестница на переменке

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

Сколько разных последовательностей шагов приведут ровно на верхнюю площадку?

Важно: ответ растёт стремительно и при больших n занимает сотни цифр — ни в какой 64-битный тип он не помещается. В Python длинная арифметика встроена: просто считай и печатай число.

Формат ввода

Одно целое число n — число ступенек.

Формат вывода

Выведи одно целое число — количество способов подняться.

Ограничения

• 1 ≤ n ≤ 4000
• Шаги только на 1 или 2 ступеньки

Пример

Ввод

5

Вывод

8

Ключевое наблюдение: последний шаг на верхнюю ступеньку мог быть только двух видов — с предыдущей ступеньки (шаг на 1) или через одну (шаг на 2). Эти варианты не пересекаются, значит количество способов складывается.

Вводим dp[i] — сколько способов оказаться ровно на ступеньке i. Тогда для i >= 2: dp[i] = dp[i-1] + dp[i-2]. Это работает, потому что любой путь до i однозначно заканчивается либо переходом из i-1, либо из i-2.

План решения:

• Заведи dp[0] = 1: «стоять перед первой ступенькой» — один способ (пустая последовательность шагов).
• dp[1] = 1: на первую ступеньку можно попасть только шагом на 1.
• Для i от 2 до n последовательно посчитай dp[i] по формуле dp[i-1] + dp[i-2].
• Выведи dp[n].
• Чтобы не хранить весь массив, достаточно двух переменных (предыдущие значения):

a, b = b, a + b.

Сложность: O(n) по времени и O(1) по памяти (если считать двумя переменными).

Частая ошибка: неправильно задать базы. Если поставить dp[0]=0, то всё «съедет», потому что пути, начинающиеся с шага на 2, перестанут учитываться корректно.