Игра в грабителя

В последнее время я рандомно выбираю задачи, которые в большинстве случаев решаются с помощью динамического программирования. Не смотря на это, к моему стыду, применить этот подход - далеко не первая моя идея при виде условий этой задачи. Но, ничего страшного, опыт и насмотренность в дальнейшем обязательно помогут сходу выявлять паттерн решения подобных задач 🙂

P.S. Для себя я сделал небольшой вывод: если вижу оптимизационную задачу, где нужно что-то максимизировать или минимизировать - перед тем как пуститься в размышления об обходе графов, стоит задать самому себе вопрос — «а применимо ли тут это самое динамическое программирование?».


Сложность: 🟠 Cредняя

ℹ️ Описание

Дан массив целых неотрицательных чисел. Каждое число — количество денег, которое может украсть грабитель из дома с соответствующим индексом. Напишите функцию, которая вернет максимальный суммарный размер грабежа, при условии, что грабитель не может ограбить два соседних дома.

⚠️ Ограничения

🔹Нельзя грабить соседние дома
🔹Кол-во домов (размер входного массива) — от 1 до 100
🔹Размер грабежа с одного дома (значения входного массива) — от 1 до 400

1️⃣ Пример

Входящие данные: [1,2,3,1]

Ответ: 4

Выгоднее всего ограбить первый и третий дом.

2️⃣ Пример

Входящие данные: [2,7,9,3,1]

Ответ: 12

В данном примере - первый, третий и пятый дома

✅ Решение

Для решения этой задачи сразу стоит выявить несколько правил:
🔹Любой маршрут грабителя должен начинаться либо с первого, либо со второго дома — так как числа в массиве неотрицательные, а в любой другой дом мы можем попасть начав машрут с одного из этих двух домов.
🔹Любой маршрут грабителя должен завершиться либо на последнем, либо на предпоследнем доме (по тем же принципам, что и в предыдущем правиле).
🔹В процессе грабителю может оказаться выгодным сменить порядок обхода домов - т.е. пропустить не один соседний дом, а сразу два. Например, вот на таких входных данных - [10,1,1,10,1,1]. В. данном случае самый выгодный маршрут — первый, четвертый и последний дома. И такая смена на длинных массивах может случаться несколько раз.

Идея решения этой задачи мало чем отличается от оптимального нахождения самого дешевого пути в матрице. По большому счету, нам нужно найти два числа - максимальный суммарный размер грабежа для маршрута, который заканчивается последним домом и маршрута, заканчивающегося на предпоследнем доме. После сравнить их между собой.

По условиям задачи и выявленным нами правилам в последний дом мы можем прийти либо из третьего дома с конца, либо из четвертого. Если мы будем знать максимальный размер грабежа машрутов, заканчивающихся на этих двух домах, задача сведется к тому, чтобы сравнить суммарные грабежи этих двух маршрутов и добавить к максимуму значение последнего дома. Тоже самое валидно и для этих двух домов. И для маршрута, заканчивающегося на предпоследнем доме.

Таким образом, так же как и в задаче на поиск пути в матрице, для решения этой задачи ам необходимо просто последовательно находить максимальный суммарный грабеж для кажого из домов (и также как в той здаче, изменения мы будем делать in-place для экономии памяти),

Алгоритм:
🔹 Запускаем цикл по исходному массиву
🔹Первые два элемента массива оставляем без изменений (так как это начала маршрутов)
🔹Третий элемент заменяем на сумму третьего и первого (так как в третий дом можно попасть только из первого)
🔹Для всех остальных элементов массива: заменяем исходное значение на сумму исходного значения и максимума из двух: значение (i-2) и (i-3) элементов, где i - индекс текущего элемента
🔹 Возвращаем максимум из двух значений: значение последнего элемента массива и значение предпоследнего элемента массива

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени
Для решения задачи нам необходимо один раз пройтись по всему исходному массиву. Итоговая сложность - O(n)

По памяти
Все изменения мы делаем in-place. Сложность по памяти константная — O(1).

#arrays #medium