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

Задача с собеседования в 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