Максимальная сумма несоседних домов
В каждом доме лежат деньги в nums. Нельзя брать из двух соседних домов. Верните максимальную сумму, которую можно взять.
Примеры: nums=[1,2,3,1] → 4 (дома 1 и 3); nums=[2,7,9,3,1] → 12 (дома 1, 3, 5). Стремитесь к O(n) времени и O(1) доп. памяти.
def rob(nums: list[int]) -> int:
# ваш код здесьНапишите реализацию.
Динамическое программирование с двумя скользящими значениями. Для каждого дома лучший итог до него — max(пропустить = лучшее_без_предыдущего, взять = лучшее_до_предыдущего + nums[i]). Хранят два скользящих значения и обновляют их на каждом доме; ответ — финальный текущий максимум. O(n) времени, O(1) памяти.
- ✗Считать дома с чётным индексом всегда оптимальными
- ✗Жадно брать наибольшие значения без учёта структуры
- ✗Забывать выбор «взять или пропустить» на каждом доме
- →Как меняется рекуррента, если дома образуют круг?
- →Почему жадный подход «крупнейшее первым» здесь неверен?
At each house you either skip it (keep the best total through the previous house) or take it (the best total two houses back, plus this house's money). Two rolling scalars suffice.
def rob(nums: list[int]) -> int:
prev = prev2 = 0 # best through last house, best through the one before
for x in nums:
prev, prev2 = max(prev, prev2 + x), prev
return prev[1,2,3,1] → take 1 and 3 → 4. [2,7,9,3,1] → take 2, 9, 1 → 12. Each house is visited once with constant extra state, so the solution is O(n) time and O(1) space.
