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

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

  1. Найти рекурсивное отношение
  2. Рекурсивный (сверху вниз)
  3. Рекурсивный + памятка (сверху вниз)
  4. Итеративный + памятка (снизу вверх)
  5. Итеративный + N переменных (снизу вверх)

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

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

Шаг 1. Выяснить рекурсивное отношение.
У грабителя есть 2 варианта: а) ограбить текущий дом i; б) не грабить текущий дом.
Если выбран вариант «а», это означает, что она не может грабить предыдущий i-1 дом, но может безопасно перейти к дому перед предыдущим i-2 и получить всю совокупную добычу, которая последует.< br /> Если выбран вариант «b», грабитель получает всю возможную добычу от ограбления i-1 и всех следующих зданий.
Итак, все сводится к расчету того, что выгоднее:

  • ограбление текущего дома + лут из домов предыдущего
  • добыча от предыдущего ограбления дома и любая добыча, захваченная до этого

rob(i) = max( rob(i - 2) + nums[i], rob(i - 1) )

Шаг 2. Рекурсивное (сверху вниз)
Преобразование рекуррентного отношения из шага 1 не должно быть очень сложным.

def rob(nums):
  return robdp(nums, nums.length - 1)
def robdp(nums, i):
  if (i < 0):
    return 0
  return max(rob(nums, i - 2) + nums[i], rob(nums, i - 1))

Этот алгоритм будет обрабатывать одно и то же i несколько раз, и его необходимо улучшить. Временная сложность: [заполнить]

Шаг 3. Рекурсивный + памятка (сверху вниз).

def rob(nums,n):
    memo = [-1]*(n+1)
    return robdp(nums, n- 1)

def robdp(int[] nums, int i): 
    if (i < 0):
        return 0
    
    if (memo[i] >= 0):
        return memo[i]
    
    result = max(rob(nums, i - 2) + nums[i], rob(nums, i - 1))
    memo[i] = result
    return result

Гораздо лучше, это должно работать за O(n) времени. Сложность пространства тоже O(n), из-за стека рекурсии попробуем от него избавиться.

Шаг 4. Итерация + памятка (снизу вверх)

def rob(nums,n):
    if (n == 0):
        return 0
    memo = [0]*(n+1)
    memo[1] = nums[0]
    for i in range(n): 
        val = nums[i]
        memo[i+1] = max(memo[i], memo[i-1] + val)
    
    return memo[n]

Шаг 5. Итерация + 2 переменные (снизу вверх)
Мы можем заметить, что на предыдущем шаге мы использовали только memo[i] и memo[i-1], поэтому возвращаемся всего на 2 шага назад. Вместо этого мы можем хранить их в двух переменных. Эта оптимизация встречается при построении последовательности Фибоначчи и некоторых других задачах [вставить ссылки].


 def rob(nums,n): 
    if (n == 0):
        return 0
    prev1 = 0
    prev2 = 0
    for num in nums: 
        tmp = prev1
        prev1 = max(prev2 + num, prev1)
        prev2 = tmp
    
    return prev1

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

Узоры

Минимальный (максимальный) путь достижения цели
Отдельные пути
Объединяющие интервалы
ДП на строках
Принятие решений

Минимальный (максимальный) путь достижения цели

Список проблем: https://leetcode.com/list/55ac4kuc

Создать постановку задачи для этого шаблона

Заявление

Для заданной цели найдите минимальные (максимальные) затраты/путь/сумму для достижения цели.

Подход

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

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Сгенерируйте оптимальные решения для всех значений в целевом объекте и верните значение для целевого объекта.

Низходящий

for j in range(n):
    result = min(result, topDown(target - ways[j]) + cost/ path / sum)

return memo[/*state parameters*/] = result;

Вверх дном

for i in range(1,target+1):
    for j in range(len(ways)):
       if (ways[j] <= i): 
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) 
       
   

 
return dp[target]

Похожие проблемы

746. Минимальная стоимость подъема по лестнице Easy

Низходящий

result = min(minCost(n-1, cost, memo), minCost(n-2, cost, memo)) + (n == cost.size() ? 0 : cost[n])
return memo[n] = result

Вверх дном

for i in range(2,n+1):
   dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i])

return dp[n]

64. Минимальная сумма пути Medium

Низходящий

result = min(pathSum(i+1, j, grid, memo), pathSum(i, j+1, grid, memo)) + grid[i][j]
    
return memo[i][j] = result

Вверх дном

for i in range(1,n):
   for j in range(1,m):
       grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
   

 
return grid[n-1][m-1]

322. Размен монет Medium

Низходящий

for i in range(len(coins)):
    if (coins[i] <= target):// check validity of a sub-problem
        result = min(ans, CoinChange(target - coins[i], coins) + 1)
    

return memo[target] = result

Вверх дном

for j in range(1,amount+1):
   for i in range(len(coins)):
       if (coins[i] <= j):
           dp[j] = min(dp[j], dp[j - coins[i]] + 1)

931. Минимальная сумма пути падения Medium

983. Минимальная стоимость билетов Medium

650. 2-клавишная клавиатура Medium

279. Идеальные квадраты Medium

1049. Последний каменный груз II Medium

120. Треугольник Medium

474. Единицы и нули Medium

221. Максимальная площадь Medium

322. Размен монет Medium

1240. Мозаика прямоугольника с наименьшим количеством квадратов Hard

174. Подземелье Hard

871. Минимальное количество остановок для заправки Hard

Отличные пути

Список проблем: https://leetcode.com/list/55ajm50i

Создать постановку задачи для этого шаблона

Заявление

Для заданной цели найдите несколько различных способов ее достижения.

Подход

Суммируйте все возможные способы достижения текущего состояния.

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

Сгенерируйте сумму для всех значений в цели и верните значение для цели.

Низходящий

for j in range(len(ways)):
    result += topDown(target - ways[j])

return memo[/*state parameters*/] = result

Вверх дном

for i in range(1,target+1):
   for j in range(len(ways)):
       if (ways[j] <= i):
           dp[i] += dp[i - ways[j]]
 
return dp[target]

Похожие проблемы

70. Восхождение по лестнице Easy

Низходящий

result = climbStairs(n-1, memo) + climbStairs(n-2, memo)
    
return memo[n] = result

Вверх дном

for stair in range(2,n+1):
   for step in range(1,3): 
       dp[stair] += dp[stair-step]

62. Уникальные пути Medium

Низходящий

result = UniquePaths(x-1, y) + UniquePaths(x, y-1)
return memo[x][y] = result

Вверх дном

for i in range(1,m):
   for j in range(1,n):
       dp[i][j] = dp[i][j-1] + dp[i-1][j]

1155. Количество бросков кубиков с заданной суммой Medium

for rep in range(1,d+1):
   new_ways=[0]*(target+1)
   for already in range(target+1):
       for pipe in range(1,f+1):
           if (already - pipe >= 0):
               new_ways[already] += ways[already - pipe]
               new_ways[already] %= mod
   ways = new_ways

Примечание

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

688. Вероятность коня на шахматной доске Medium

494. Целевая сумма Medium

377. Комбинация Сумма IV Medium

935. Рыцарь Звонилка Medium

1223. Моделирование броска игральных костей Medium

416. Сумма равного подмножества разделов Medium

808. Порции супа Medium

790. Домино и Тромино Тайлинг Medium

801. Минимальные свопы для увеличения последовательности

673. Номер самой длинной возрастающей подпоследовательности Medium

63. Уникальные пути II Medium

576. Вне пограничных путей Medium

1269. Количество способов остаться на том же месте после нескольких шагов Hard

1220. Подсчитайте перестановку гласных Hard

Объединение интервалов

Список проблем: https://leetcode.com/list/55aj8s16

Создать постановку задачи для этого шаблона

Заявление

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

Подход

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

// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

Получите лучшее из левой и правой сторон и добавьте решение для текущей позиции.

for l in range(1,n):
   for i in range(n-l):
       j = i+l
       for k in range(i,j):
           dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j])
return dp[0][n-1]

Похожие проблемы

1130. Дерево минимальной стоимости из конечных значений Medium

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       dp[i][j] = sys.maxsize
       for k in range(i,j):
           dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + maxs[i][k] * maxs[k+1][j])

96. Уникальные бинарные деревья поиска Medium

1039. Минимальная оценка триангуляции полигона Medium

546. Удалить коробки Medium

1000. Минимальная стоимость объединения камней Medium

312. Лопающиеся шары Hard

375. Угадай число больше или меньше II Medium

ДП на струнах

Список проблем: https://leetcode.com/list/55afh7m7

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

Заявление

По двум строкам s1 и s2 вернуть some result.

Подход

Большинство задач в этом шаблоне требуют решения, приемлемого по сложности O(n²).

// i - indexing string s1
// j - indexing string s2
for i in range(1,n+1):
   for j in range(1,m+1):
       if (s1[i-1] == s2[j-1]):
           dp[i][j] = /*code*/;
       else:
           dp[i][j] = /*code*/;

Если вам дана одна строка s, подход может незначительно отличаться

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       if (s[i] == s[j]):
           dp[i][j] = /*code*/;
       else:
           dp[i][j] = /*code*/;

1143. Самая длинная общая подпоследовательность Medium

for i in range(1,n+1):
   for j in range(1,m+1):
       if (text1[i-1] == text2[j-1]):
           dp[i][j] = dp[i-1][j-1] + 1
       else:
           dp[i][j] = max(dp[i-1][j], dp[i][j-1])

647. Палиндромные подстроки Medium

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       if (s[i] == s[j] && dp[i+1][j-1] == j-i-1):
           dp[i][j] = dp[i+1][j-1] + 2
       else:
           dp[i][j] = 0;

516. Самая длинная палиндромная последовательность Medium

1092. Кратчайшая общая суперпоследовательность Medium

72. Редактировать расстояние Hard

115. Отдельные подпоследовательности Hard

712. Минимальная сумма удаления ASCII для двух строк ​​Medium

5. Самая длинная палиндромная подстрока Medium

Принятие решения

Список проблем: https://leetcode.com/list/55af7bu7

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

Заявление

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

Подход

Если вы решите выбрать текущее значение, используйте предыдущий результат, в котором значение было проигнорировано; и наоборот, если вы решите игнорировать текущее значение, используйте предыдущий результат, в котором использовалось значение.

// i - indexing a set of values
// j - options to ignore j values
for i in range(1,n):
   for j in range(1,k+1):
       dp[i][j] = max(dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1])
       dp[i][j-1] = max(dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i])

198. Грабитель домов Easy

for i in range(1,n):
   dp[i][1] = max(dp[i-1][0] + nums[i], dp[i-1][1])
   dp[i][0] = dp[i-1][1]

121. Лучшее время для покупки и продажи акций Easy

714. Лучшее время для покупки и продажи акций с комиссией за транзакцию Medium

309. Лучшее время для покупки и продажи акций с кулдауном Medium

123. Лучшее время для покупки и продажи акций III Hard

188. Лучшее время для покупки и продажи акций IV Hard

Надеюсь, эти советы будут полезны 😊