Это вопрос кодирования. Однако я не требую ответа в коде. Мне просто нужна помощь в выяснении математики, стоящей за этим вопросом.
Вы профессиональный грабитель, планирующий грабить дома вдоль улицы. В каждом доме припрятана определенная сумма денег, единственное ограничение, мешающее вам ограбить каждый из них, - это то, что соседние дома имеют подключенную систему безопасности, и она автоматически свяжется с полицией, если два соседних дома были взломаны в одну и ту же ночь.
Учитывая список неотрицательных целых чисел, представляющих сумму денег в каждом доме, определите максимальную сумму денег, которую вы можете ограбить сегодня вечером, не предупредив полицию.
Примечание: "список" на самом деле представляет собой массив целых чисел, где индекс элемента означает положение дома, а элемент-сумму денег, спрятанных в нем. Грабитель не может грабить соседние индексы. В качестве примера массив выглядит следующим образом
[10 50 7 15 500 100]
Что я уже пробовал:
Я думал просто сложить альтернативные элементы, но эта логика не даст правильного результата для многих случаев, особенно для образца, который я включил в свой вопрос. Правильный ответ в этом случае - просто сложить 500 и 50.
Richard MacCutchan
Математика довольно проста, сначала вы идете за 500, так как это самое высокое значение, а затем смотрите, к каким другим домам можно получить доступ.
W∴ Balboos, GHB
Начинать с самого большого не обязательно как общее решение! Предположим, что 500 находится между двумя 400-ми ?
Мой первый инстинкт-следовать правилу несмежности и делать все юридические перестановки , отмечая, что некоторые могут оставить два соседних дома без посещения.
Richard MacCutchan
Вы, конечно, правы. Мой ответ был чрезмерным упрощением.
Member 13192781
Спасибо вам всем за помощь.