Harddp
Что такое динамическое программирование?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
DP — метод решения через разбиение на overlapping подзадачи и сохранение результатов. Два подхода: top-down (memoization) и bottom-up (tabulation).
# Top-down: рекурсия + cache
def fib(n, memo={}):
if n < 2: return n
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n] # O(n) вместо O(2^n)
# Bottom-up: итеративно
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) время, O(1) памятьПризнаки DP-задачи: optimal substructure + overlapping subproblems. Типичные: Knapsack 0/1, Longest Common Subsequence, Coin Change, Edit Distance, Climbing Stairs. Space optimization — часто можно сократить dp[i] до нескольких переменных. DP ≠ greedy: greedy даёт suboptimal, DP exhaustive.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.