#198 Грабитель дома

Проблема



House Robber - LeetCode
Вы профессиональный грабитель, планирующий ограбить дома на улице. В каждом доме спрятана определенная сумма денег…leetcode.com



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

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

Пример 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Пример 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Псевдокод

Глядя на диаграмму, мы можем сделать вывод, что:

maxLoot = []
maxLoot[0] = 2
maxLoot[1] = Math.max( houses[1], houses[0] )
----- patterns appears from now on -----
maxLoot[2] = Math.max( houses[1], houses[2] + houses[0] )
maxLoot[3] = Math.max( houses[2], houses[3] + houses[1] )
maxLoot[4] = Math.max( houses[3], houses[4] + houses[2] )
----- translate into logic -----
maxLoot[i] = Math.max( houses[i - 1], houses[i] + houses[i - 2] )

Код

Ссылка