Climbing Stairs (Подъём по лестнице)
Описание: Вы поднимаетесь по лестнице из n ступеней. За один шаг можно подняться на 1 или на 2 ступени. Сколькими различными способами можно добраться до вершины?
Пример 1:
Вход: n = 5
Выход: 8
Объяснение: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1
Пример 2:
Вход: n = 2
Выход: 2
Объяснение: 1+1 и 2
Ограничения:
1 <= n <= 45
Рекомендуемая временная и пространственная сложность
Стремитесь к решению за O(n) по времени и O(1) по памяти.
Подсказка 1
Подумайте, откуда можно попасть на ступень n. Только с ступени n-1 (шагом в одну) или со ступени n-2 (шагом в две).
Подсказка 2
Значит количество способов добраться до n равно сумме способов добраться до n-1 и n-2. Узнаёте последовательность?
Подсказка 3
Это числа Фибоначчи. Хранить весь массив не нужно — достаточно двух последних значений.