House Robber (Дом грабителя)
Описание: Дан массив с суммами денег в домах, стоящих в ряд. Нельзя грабить два соседних дома. Верните максимальную сумму, которую можно унести.
Пример 1:
Вход: nums = [2,7,9,3,1]
Выход: 12
Объяснение: Берём дома 0, 2 и 4: 2 + 9 + 1 = 12
Пример 2:
Вход: nums = [1,2,3,1]
Выход: 4
Объяснение: Берём дома 0 и 2: 1 + 3 = 4
Ограничения:
1 <= nums.length <= 100
0 <= nums[i] <= 400
Рекомендуемая временная и пространственная сложность
Стремитесь к O(n) по времени и O(1) по памяти.
Подсказка 1
Для каждого дома есть два варианта: ограбить его или пропустить.
Подсказка 2
Если грабим дом i, к нему прибавляется лучший результат до i−2. Если пропускаем — берём лучший результат до i−1.
Подсказка 3
Значит нужны только два предыдущих значения, весь массив хранить незачем.