Динамическое программирование

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

House Robber:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

На основании постановки задачи зададим начальные условия:

  1. если дома нет, грабитель не сможет украсть деньги
  2. если есть только один дом, грабитель может украсть только этот дом
  3. если есть два или более домов, грабитель попытается украсть максимальную сумму денег, не крадя из двух соседних домов
condition #1 and #2
var rob = function(nums) {
   const length = nums.length
   if(length === 0){
      return 0
   } else if(length === 1){
      return nums[0]
   }
}

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

[ 1, 3, 4, 4, 3, 3, 7, 2, 3, 4, 5, 1 ]

Сравним сумму, которую грабитель может украсть из первого и второго домов.

1 or 3 ? 3 is bigger, so the robber will go to steal 3

В третьем доме грабитель задумается, что лучше украсть: 3 или 1 + 4 = 5. Грабитель украдет 5, так как это большее число. Затем грабитель решит, украсть ли ему 5 или 3 + 4 = 7. Грабитель пойдет на 7 и так далее. Это обозначение можно записать следующим образом:

  1  3  5  7  8 10 15 15 18 19 23 23
[ 1, 3, 4, 4, 3, 3, 7, 2, 3, 4, 5, 1 ]

Обратите внимание, что начиная с третьего дома, мы сравнили числа [i] + nums [i-2] и nums [i-1], чтобы увидеть, какой выбор может быть максимальным. Если преобразовать эту логику в код:

var rob = function(nums) {
    const length = nums.length
    if(length === 0) {
        return 0
    } else if(length === 1) {
        return nums[0]
    }
 
   //          1  3  5  7  8 10 15 15 18 19 23 23
   // nums = [ 1, 3, 4, 4, 3, 3, 7, 2, 3, 4, 5, 1 ]
const house = []
    house[0] = nums[0] // 1
    house[1] = Math.max(nums[0], nums[1]) // 3
    
    for (let i = 2; i < length; i++) {
        house[i] = Math.max(nums[i] + house[i - 2], house[i - 1]);
     // house[2] = Math.max(nums[2] + house[0]), house[1]) => 5
     // house[3] = Math.max(nums[3] + house[1]), house[2]) => 7
     // house[4] = Math.max(nums[4] + house[2]), house[3]) => 8
    }
return house[length - 1];
// house = [1,  3,  5,  7,  8, 10, 15, 15, 18, 19, 23, 23]
};

источник:

Https://www.geeksforgeeks.org/dynamic-programming/

Https://leetcode.com/problems/house-robber/