Проблема
Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятана определенная сумма денег, единственное ограничение, мешающее вам ограбить каждый из них, заключается в том, что в соседних домах подключены системы безопасности, и он автоматически свяжется с полицией, если два соседних дома будут взломаны в одну и ту же ночь.
Дан целочисленный массив 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.
Ограничения:
1 <= nums.length <= 100
0 <= nums[i] <= 400
Решение
На первый взгляд, это кажется очень простым. Верните большую из двух сумм: все дома с нечетными номерами или все дома с четными номерами. Ни одна из этих проблем не является такой простой, поэтому я подумал о пограничном случае, который не прошел бы эту текущую логику.
Для этого теста выгоднее пропустить два дома подряд. Нет смысла пропускать более двух домов, так как вы без необходимости пропускаете дом с достаточным расстоянием.
Для этой задачи можно использовать рекурсивный подход, но ограничение по времени будет превышено для больших входных данных.
- Проверьте, есть ли на входе доступные дома, если нет, верните 0
- Создайте массив для запоминания наших значений при повторении ввода. Он должен быть той же длины, что и ввод
- В этом новом массиве загрузите нулевой индекс с нулевым значением индекса из nums и установите первый индекс нового массива равным значению, которое больше между нулем и первым индексом ввода.
- Поскольку мы заполнили первые 2 значения, мы можем начать нашу итерацию со второго индекса. На каждой итерации нам нужно будет присвоить значение arr[i] большему из двух значений: либо предыдущее значение arr[i-1], либо arr[i-2] + nums[i]. Это переназначение позволяет нам запомнить больший из двух вариантов. Это обеспечивает значительную экономию времени по сравнению с рекурсивным подходом.
- Нашей наибольшей суммой будет последнее значение в обр.