UniLecs #Task. Robber
Задача: грабитель, планирует обчистить дома на улице. В каждом доме на этой улице спрятана определенная сумма денег. Все дома на этой улице расположены по кругу, т.е. 1й дом является соседом последнего.
Также в соседних домах есть сигнализация, и она автоматически сработает, если в одну ночь взломают два соседним дома.
Зная сумму денег в каждом доме, вам необходимо обчистить дома с максимальным уловом, при этом сигнализация не должна сработать.
Входные данные: arr — сумма положительных целых чисел, представляющих сумму денег в iм доме.
Вывод: profit — максимально возможный улов грабителя без срабатывания сигнализации.
Примеры:
- arr = [2, 3, 2]
Output: 3 (нельзя ограбить 1й и 3й дом, т.к. они также являются соседними из-за круговой улицы). - arr = [1,2,3,1]
Output: 4 (грабим 1й и 3й дом)
Разбор
Заметим, что для прямой улицы есть нектр закономерность для простых случаев:
- Один дом на улице, то ответ — стоимость этого дома.
- Два дома, то ответ — это Max(house1, house2).
- Три дома, то можно выбрать средний дом или сумму первого и последнего домов. То есть Max(house3 + house1, house2).
Отсюда можно вывести общую формулу для метода динамического программирования: dp[i] = Max(dp[i — 1], dp[i — 2] + nums[i]).
Также следует учесть, что улица круговая. Это значит, что отсчет мы можем начать либо с 1го дома и тогда последний дом не будет включен в подсчет. Либо начать отсчет со 2го дома и тогда последний дом будет включен в подсчет. То есть отдельно подсчитаем оба варианта и выберем оптимальный. Детали реализации смотрите в коде.
Реализация
https://gist.github.com/unilecs/c3300573943dc0ada0937c2f4ff6b607
