Грабитель домов: рекуррентное решение «взять или пропустить»

В задаче «Грабитель» дан массив неотрицательных целых чисел, обозначающих сумму денег в каждом доме. Требуется найти максимальную сумму, которую можно украсть, не грабя два соседних дома. Например, для [2, 7, 9, 3, 1] результат равен 12: нужно ограбить дома 0, 2 и 4. Это классическая задача на одномерный DP, где на каждом шаге принимается бинарное решение.

Пусть dp[i] — максимальная сумма, украденная из первых i+1 домов. В каждом доме i есть два варианта: пропустить его и взять dp[i-1] или ограбить его и взять nums[i] + dp[i-2]. Рекуррентное соотношение: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Это фундаментальный шаблон выбрать или пропустить, который встречается во многих задачах на DP.

Для [2, 7, 9, 3, 1] проследим за таблицей: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. Итоговый ответ — dp[4] = 12. Ручное прохождение таблицы подтверждает, что рекуррентное соотношение корректно обрабатывает выбор и пропуск на каждой позиции.

Таблица DP обращается только к двум предыдущим позициям, поэтому весь массив можно заменить двумя переменными: prev2 — значение два шага назад и prev1 — значение один шаг назад. После каждой итерации сдвигайте их: prev2 = prev1 и prev1 = current. Это уменьшает объём памяти с O(n) до O(1), сохраняя временную сложность O(n).

Всегда проверяйте решение на крайних случаях: пустой массив — вернуть 0, массив из одного элемента — вернуть этот элемент, массив из двух элементов — вернуть максимум из двух. На собеседовании упоминание и обработка этих случаев демонстрируют основательность. Проверка if n == 1 предотвращает выход за границы индекса при обращении к nums[1] для dp[1].

В круговом варианте (LeetCode 213) дома расположены по кругу, поэтому первый и последний дома являются соседними. Нельзя напрямую применить линейное рекуррентное соотношение. Ключевая идея: либо Вы грабите первый дом и не грабите последний, либо не грабите первый и грабите последний. Запустите линейное решение задачи о грабителе для обоих подмассивов и возьмите максимум.

Наивный жадный подход может заключаться в том, чтобы всегда грабить самый дорогой доступный дом. Однако он не работает на таких входных данных, как [2, 1, 1, 2]: жадный подход выбирает дом 0 со значением 2, затем дом 3 со значением 2, получая сумму 4, а ограбление домов 0 и 2 даёт 3. Но подождите — в этом случае жадный подход работает! Рассмотрим [1, 3, 1, 3, 100]: жадный подход выбирает дома со значениями 3 и 3, то есть с индексами 1 и 3, получая 6, и упускает оптимальные 1+1+100=102. Необходим DP, поскольку локально оптимальные решения не гарантируют глобальный оптимум.

Шаблон «выбрать или пропустить» применяется не только к задаче о грабителе. Каждый раз, когда Вы проходите по массиву и на каждой позиции выбираете между включением текущего элемента с пропуском предыдущего и исключением текущего элемента с сохранением предыдущего результата, перед Вами DP по шаблону «выбрать или пропустить». Ищите ограничения вроде никаких двух соседних элементов или никаких пересекающихся интервалов — они указывают на применение этого шаблона.

Удаление и получение очков (LeetCode 740): за каждое выбранное число начисляется num × count(num), но при этом необходимо удалить все вхождения num-1 и num+1. Эта задача напрямую сводится к задаче о грабителе: постройте массив earn[v] = v × count(v) для всех значений, затем примените к этому массиву решение задачи о грабителе. Умение распознавать такие сведения к знакомым задачам — важный навык на собеседовании.

В задаче «Грабитель III» дома расположены в виде двоичного дерева. Нельзя одновременно ограбить узел и его непосредственного родителя. Определите вспомогательную функцию, возвращающую два значения: rob(node) → (rob_root, skip_root). Если Вы грабите корень, сложите значения пропуска для обоих дочерних узлов. Если Вы пропускаете корень, сложите лучшие результаты для каждого дочернего узла. Это обход DFS в постпорядке с решением выбрать или пропустить на каждом узле.

Линейное решение задачи о грабителе выполняется за время O(n) и использует память O(1) благодаря оптимизации с двумя переменными. Круговой вариант также выполняется за время O(n), поскольку дважды вызывает линейную версию. Вариант с деревом выполняется за время O(n) и использует память O(h), где h — высота дерева. На собеседовании всегда называйте сложность после написания кода и упоминайте оптимизацию памяти — это показывает, что Вы думаете не только о первом работающем решении.

Проверьте, насколько Вы понимаете концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», рассмотренные в этом уроке.

В этом уроке Вы узнали: рекуррентное соотношение «взять или пропустить» dp[i] = max(dp[i-1], nums[i] + dp[i-2]), сведение пространственной сложности O(n) к O(1) с помощью двух переменных, значения которых обновляются по ходу вычислений и расширение этого подхода на циклические массивы и двоичные деревья. Далее мы рассмотрим задачи о подмассиве с максимальной суммой и подмассиве с максимальным произведением с использованием алгоритма Кадане.