House Robber

Средняя№198одномерный массив

Дома стоят в ряд, в каждом лежат деньги. Нужно унести как можно больше, но не из двух соседних домов: сработает сигнализация. Наш пример: [6, 2, 1, 7, 4, 3] — не больше 16, из 6, 7 и 3.

198 House RobberРазбор · 1×

Пример: [6, 2, 1, 7, 4, 3]. Смотрите на дом 4: в нём есть деньги, и всё же его выгоднее не трогать.

домаbest061221374453
этот шагзаполненоберём отсюда, грабимне грабим, не выбраноответ

Таблица из 7 клеток: best[i] — больше всего денег из первых i домов

01/24
сначала · назад · пуск · шаг
Скорость
1function rob(houses):
2 best = new array of size len(houses) + 1
3 best[0] = 0 // no houses yet
4 best[1] = houses[0]
5 for i from 2 to len(houses):
6 skip = best[i - 1] // leave house i - 1
7 take = best[i - 2] + houses[i - 1]
8 best[i] = max(skip, take)
9 return best[len(houses)]
состояние
best
[–, –, –, –, –, –, –]
i
–
skip
–
take
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Посмотрим на последний дом из первых i: либо его не трогают, и лучшее — как для первых i − 1, либо его грабят, и тогда соседа нет, значит, лучшее для первых i − 2 плюс его деньги. Других вариантов нет.
  2. Грабить дом выгодно не всегда: дом 4 даёт 4, но тогда нельзя взять 7 рядом с ним, и 6 + 1 + 4 = 11 проигрывает 6 + 7 = 13 без него.
  3. Перебор пробует все наборы домов, их около 2ⁿ. Таблица хранит одно лучшее значение на префикс, и каждое строится из двух прежних клеток.

Сложность

Время O(n): по клетке на дом, каждая из двух прежних. Память O(n) на таблицу; читаются только две последние клетки, так что двумя переменными можно довести до O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.