Blind 75 — Вопросы по программированию и техническому интервью — серия объяснений
Проблема:
Объяснение:
Код для этой задачи очень прост, но интуиция сложнее кода. Всегда есть решение грубой силы, но оно равно O(n²) и является тривиальным. Это задача динамического программирования, которая помогает при поиске решения. Решение, которое не требует массива и, следовательно, пространства O(1), заключается в отслеживании количества шагов 1 и шагов 2. Если вы знаете классические функции, это просто последовательность Фибоначчи. Возможность установить эту связь является ключом к решению этой проблемы наиболее эффективным способом.
Решение для динамического программирования: O(n)
Сначала инициализируйте одношаговые и двухшаговые переменные, затем от i до n минус два (записывается как n-1, но n-1 не включено). Затем мы сохраняем одну переменную, добавляем две переменные, затем устанавливаем две в одну. Повторение этого и возвращение одного, а не двух, потому что это предполагает, что вы можете сделать два шага от n-1 до n, даст нам результат.
class Solution: def climbStairs(self, n: int) -> int: one, two = 1, 1 for i in range(n — 1): tmp = one one += two two = tmp return one
Информация:
Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]
