Основы динамического программирования — Табулирование
Есть два метода решения проблемы с помощью динамического программирования. В этом посте мы увидим метод табуляции. Пожалуйста, обратитесь к моим основам динамического программирования — часть 1 для метода мемоизации.
- Мемоизация
- Табулирование
Что такое динамическое программирование?
Это метод оптимизации по сравнению с простой рекурсией. Это значительно сокращает время, необходимое для решения проблемы для данного ввода. Он разбивает проблему на вложенные подзадачи и вычисляет результат для этих подзадач. Эти результаты подзадач повторно используются, чтобы избежать повторного вычисления. Это снижает временную сложность задачи с экспоненциальной до полиномиальной. Такое повторное использование результатов подзадач можно осуществить двумя способами — запоминанием и табулированием.
Что такое табулирование?
Структура данных определенного размера инициализируется значениями по умолчанию на основе требований и повторяется только один раз для вычисления конечного результата. В конце итерации можно получить результат.
С табулированием:
Постановка задачи. Следующая функция принимает два аргумента — 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))
Вывод:
Используя табулирование, мы сокращаем время выполнения. Это помогает ускорить выполнение и избежать ошибки нехватки памяти.