Динамічне програмування - це методика комп'ютерного програмування, яка допомагає ефективно вирішувати клас завдань, що мають підзавдання, що перекриваються, і оптимальні властивості підструктури.
Такі проблеми включають багаторазове обчислення значення одних і тих же підзадач для знаходження оптимального рішення.
Приклад динамічного програмування
Візьмемо випадок генерації послідовності Фібоначчі.
Якщо послідовність F(1) F(2) F(3) ........ F(50), то слідує правило F(n) = F(n-1) + F(n-2)
F(50) = F(49) + F(48)
F(49) = F(48) + F(47)
F(48) = F(47) + F(46)
...
Зверніть увагу, що тут існують підзавдання, що перекриваються, тому що нам потрібно обчислити F (48), щоб обчислити, як F (50), так і F (49). Це саме той алгоритм, де добре видно приклад динамічного програмування.
Як працює Динамічне програмування
Динамічне програмування працює шляхом збереження результатів підзавдань, щоб, коли їх вирішення, вони були під рукою, і нам не потрібно було їх перераховувати.
Ця техніка зберігання значення підзавдання називається мемоізацією (запам'ятовуванням) . Зберігаючи значення в масиві, ми заощаджуємо час для обчислень підзадач, з якими ми вже стикалися.
var m = map(0 → 0, 1 → 1)
function fib(n)
if key n is not in map m
m[n] = fib(n − 1) + fib(n − 2)
return m[n]
Динамічне програмування шляхом мемоізації - це низхідний підхід до динамічного програмування. Змінивши напрямок, у якому працює алгоритм, тобто почавши з базового випадку та працюючи над рішенням, ми можемо також використовувати Динамічне програмування «знизу вгору».
function fib(n)
if n = 0
return 0
else
var prevFib = 0, currFib = 1
repeat n − 1 times
var newFib = prevFib + currFib
prevFib = currFib
currFib = newFib
return currentFib
Рекурсія vs Динамічного програмування
Динамічне програмування переважно застосовується до рекурсивним алгоритмам. Це не збіг, більшість завдань оптимізації потребують рекурсії, а для оптимізації використовується динамічне програмування.
Але не всі завдання, що використовують рекурсію, можуть використовувати динамічне програмування. Якщо немає підзадач, що перекриваються, як у випадку послідовності Фібоначчі, рекурсія може досягти рішення тільки з використанням підходу «поділяй і володарюй» .
З цієї причини рекурсивний алгоритм, такий як «Сортування злиттям», не може використовувати динамічне програмування, оскільки підзавдання жодним чином не перекриваються.
Жадібні алгоритми vs Динамічного програмування
Жадібні алгоритми схожі на динамічне програмування в тому сенсі, що вони є інструментами для оптимізації.
Однак жадібний алгоритм шукає локально оптимальне рішення або, іншими словами, «жадібний» вибір, сподіваючись знайти глобальний оптимум. Отже, жадібні алгоритми можуть зробити припущення, яке виглядає оптимально, але водночас стає дорогим і гарантує перебування глобального оптимуму.
Динамічне програмування, з іншого боку, знаходить оптимальне рішення для підзавдань, а потім робить усвідомлений вибір, комбінуючи результати цих підзавдань, щоб знайти оптимальне рішення.
