Основы динамического программирования — Табулирование

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

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

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

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

Что такое табулирование?

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

С табулированием:

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

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

С объяснением кода табуляции:

Например, таблица(7,Массив(5,4,3))

Инициализация массива со значениями по умолчанию:

0 верно для любого случая, так как targetSum 0 возможен для любой комбинации.

Итерация по каждому элементу массива для обновления значений:

Для индекса 0:

Для индекса 1:

Для индекса 2:

Для индекса 3:

Для индекса 4:

Для индекса 5:

Для индекса 6:

Для индекса 7:

Массивы обновляются значениями, а массивы с T означают, что их индекс возможен с комбинацией (суммой) одного или нескольких элементов в массиве. Конечный массив значений (targetSum), т.е. arr(7) в нашем примере, возвращает результат.

def table(targetSum: Int, arr: Array[Int]):Boolean={
 val tbl: Array[Boolean]=Array.ofDim(targetSum+1)
 tbl(0)=true
 var i=0
 while(i<=targetSum){
 if(tbl(i)==true){
 arr.foreach(j=>{if (i+j <= targetSum) tbl(i+j)=true})
 }
 i=i+1
 }
 tbl(targetSum)
}
table(7,Array(9,10,7))
table(300,Array(7,14))

Вывод:

Используя табулирование, мы сокращаем время выполнения. Это помогает ускорить выполнение и избежать ошибки нехватки памяти.