Существует n количество домов (1,2,3, ..., n). Вор должен начать с дома 1 и добраться до дома n, чтобы украсть максимум. Он может украсть дом, и он может уйти. Если он вообще украл в любом доме, хозяин дома сообщит соседям слева и справа. Сколько максимум он может украсть ..Найти Максимальные значения, которые могут быть получены от N
как мы можем решить с помощью динамического программирования ..
Пусть arr[0..n-1] обозначает число портов для каждого из хостов из 1 в n.
В любой момент у вас есть два варианта: сканировать все порты для текущего хоста или не проверять порты для текущего хоста.
Позвольте dp[] быть результирующим массивом.
Очевидно,
dp[i] = max(dp[i-1], arr[i] + dp[i-2])
dp[i-1] для случая, когда вы не сканировать порты. arr[i] + dp[i-2] при сканировании портов для текущего хоста. В этом случае вы не можете добавить dp[i-1] из-за ограничения, что последовательные хосты не могут быть отсканированы. Поэтому мы добавляем dp[i-2].
Вашего окончательный ответ dp[n-1]
Надеется, что это помогает !!
Редактировать: Ниже вопрос совпадает с вашими:
Есть ˝n˝ домов, построенных в линию, каждый из которых содержит некоторое значение в нем. Вор собирается украсть максимальную ценность в этих домах, но он не может украсть в двух смежных домах, потому что владелец похищенного дома скажет своим двум соседям по левой и правой стороне. Какова максимальная украденная стоимость?
Найти решение here