Задача с собеседования в Zoho

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

Пример 1:
Input: n = 2
Output: 2
Explanation: Существует два способа подняться на вершину:
1. 1 шаг + 1 шаг
2. 2 шага

Пример 2:
Input: n = 3
Output: 3
Explanation: Существует три способа подняться на вершину:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг

Ограничения:
1 <= n <= 45

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming", оптимальным вариантом решения будет использование восходящего подхода с табуляцией, так мы избавимся от риска переполнения стека при глубокой рекурсии. Для оптимизации памяти до O(1) храним только две переменные (cur_step и prev_step) вместо dp массива.
Начинаем с базовых случаев (ступеньки 0 и 1), при которых ответ будет равен 1 способу => инициализируем наши две переменные значениями 1.
Запускаем цикл и поднимаемся вверх по лестнице со второй ступеньки, обновляя значения кол-ва способов подняться на предыдущую и текущую ступеньки, с каждой итерацией:
- текущая ступенька становится предыдущей;
- новая текущая ступенька равняется сумме способов подняться на две предыдущие ступеньки (по сути, классическая формула из задач о числах Фибоначчи: f(n) = f(n-1) + f(n-2)).
После окончания работы цикла выводим cur_step с последним вписанным в переменную значением.

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

Код
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1

cur_step, prev_step = 1, 1

for _ in range(2, n + 1):
prev_step, cur_step = cur_step, prev_step + cur_step

return cur_step

@algoses