Проблема

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

Дан целочисленный массив 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

Решение

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

Для этого теста выгоднее пропустить два дома подряд. Нет смысла пропускать более двух домов, так как вы без необходимости пропускаете дом с достаточным расстоянием.

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

  1. Проверьте, есть ли на входе доступные дома, если нет, верните 0
  2. Создайте массив для запоминания наших значений при повторении ввода. Он должен быть той же длины, что и ввод
  3. В этом новом массиве загрузите нулевой индекс с нулевым значением индекса из nums и установите первый индекс нового массива равным значению, которое больше между нулем и первым индексом ввода.
  4. Поскольку мы заполнили первые 2 значения, мы можем начать нашу итерацию со второго индекса. На каждой итерации нам нужно будет присвоить значение arr[i] большему из двух значений: либо предыдущее значение arr[i-1], либо arr[i-2] + nums[i]. Это переназначение позволяет нам запомнить больший из двух вариантов. Это обеспечивает значительную экономию времени по сравнению с рекурсивным подходом.
  5. Нашей наибольшей суммой будет последнее значение в обр.