Easydp
Решить задачу Climbing Stairs (LeetCode 70)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 70. Сколькими способами взобраться по лестнице из n ступеней, делая 1 или 2 шага? Это числа Фибоначчи: dp[n] = dp[n-1] + dp[n-2]. O(n) время, O(1) память.
def climbStairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bПростое рекурсивное O(2ⁿ) — слишком медленное; memoization делает O(n). Вариации: Min Cost Climbing Stairs (746) — каждый шаг имеет cost; шаги из множества steps[] — DP по сумме. Классика DP — первый вопрос, показывает как из рекурсии получить O(n).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.