Mediumdp
Решить задачу House Robber (LeetCode 198)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 198. Грабитель не может ограбить два соседних дома. DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). O(n) время, O(1) память.
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
cur = max(prev1, prev2 + nums[i])
prev2, prev1 = prev1, cur
return prev1Для каждого дома: ограбить (+nums[i], пропускаем предыдущий) или пропустить (dp[i-1]). Вариации: House Robber II (213) — дома по кругу: max(rob(nums[1:]), rob(nums[:-1])); House Robber III (337) — tree DP через post-order.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.