Основы динамического программирования

Основы динамического программирования — часть 1

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

Мемоизация
Табулирование

Что такое динамическое программирование?

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

Что такое мемоизация?

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

Давайте продемонстрируем метод на простом примере (не регулярная генерация последовательности Фибоначчи) в Scala. В Scala недостаточно ресурсов для динамического программирования, поэтому я надеюсь, что это будет полезно.

Как решить ту же задачу методом табуляции, будет рассказано в посте «Основы динамического программирования — часть 2». Пожалуйста, не стесняйтесь проверить это.

Без мемоизации:

Постановка задачи. Следующая функция принимает два аргумента — targetSum и массив элементов Integer и возвращает значение true, если любая комбинация элементов массива может суммироваться до targetSum. Комбинация может быть любым числом из массива, рассмотренным любое количество раз.

Например, targetSum:3 , arr:Array(1,4,7) => возвращает true, поскольку 1+1+1=3

Без объяснения кода мемоизации:

Каждый раз, когда targetSum обновляется, рекурсивно вычитая элементы из массива, и смотрите, не привела ли хотя бы одна комбинация к 0 (это означает, что комбинация может суммироваться до targetSum). Если это так, возвращаемое значение функции истинно.

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

def recursion(targetSum: Int, arr: Array[Int]):Boolean={
     if(targetSum == 0) true
     else if(targetSum < 0) false
     else{
     arr.map(i=>{
     var temp=targetSum-i
     recursion(temp,arr)
     }).exists(j=>j==true)
     } 
     
recursion(7,Array(5,3,4,7))
recursion(300,Array(7,14)) // slows down the runtime

С мемоизацией:

С объяснением кода для запоминания:

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

import scala.collection.mutable.Map
def recursion_memoized(targetSum: Int, arr: Array[Int],memo:Map[Int, Boolean]):Boolean={
if(targetSum == 0) true
else if(targetSum < 0) false
else if(memo.contains(targetSum)) memo(targetSum)
else{
 arr.map(i=>{
 var temp=targetSum-i
 memo(targetSum)=recursion_memoized(temp,arr,memo)
 memo(targetSum)
}).exists(j=>j==true)
}
}
recursion_memoized(7,Array(5,3,4,7),Map())

Вывод:

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

Основы динамического программирования — Часть 1