Чи доводилося вам раніше у процесі вивчення математики або фізики розбивати складну задачу на декілька дрібніших однотипних задач?

Динамічне програмування — це метод розв’язування задач, що мають певні властивості, шляхом їх розбиття на декілька однотипних підзадач, пов’язаних між собою.

Динамічне програмування — розділ математичного програмування, що вивчає багатокрокові процеси пошуку оптимального вирішення складних завдань. Застосовується при складанні програм рішення таких задач оптимізації, для яких процес пошуку рішення можна представити у вигляді деякої послідовності кроків, тобто знаходять оптимальне рішення на кожному кроці процесу і таким чином зводять рішення однієї складної задачі до  вирішення великого числа значно менш складних.

До задач оптимізації відносять задачі пошуку максимальних або мінімальних значень певних функцій. Наприклад, пошуку максимального значення прибутку від інвестування у відповідну галузь за багаторічний період зводиться до послідовного визначення оптимальних капіталовкладень на кожен рік.

Загальним для задач динамічного програмування є те, що змінні в моделі розглядаються не разом, а послідовно, одна за одною, тобто будується така обчислювальна схема, коли замість одного завдання з багатьма змінними використовують багато завдань з малим числом (зазвичай навіть однієї) змінних у кожній. Це значно скорочує обсяг обчислень. Пояснимо сутність динамічного програмування на найпростішому прикладі 1.

Приклад 1. Нехай потрібно обчислити суму n чисел: 1+ 2+ 3+ 4 +...+ n. Складність цієї задачі полягає в тому, що необхідно одразу взяти велику кількість чисел і додати їх. Можна спочатку визначити суму першого елемента, тобто просто взяти перший елемент: f (1)=1 . Потім до суми можна додати другий елемент: f (2)=f (1) + 2= 3. Аналогічно отримуємо: f (3) = f (2) + 3= 6, f (n) =  f (- n) 1 + n.

Приклад 2. Припустимо, що компанія виготовляє процесори (позначимо їх змінною х1), системні плати (х2), монітори (х3) та інші пристрої. Для визначення максимального прибутку потрібно визначити, яку кількість пристроїв слід виготовити, скільки потрібно мати персоналу тощо. Знайти розв’язок цієї задачі за великої кількості змінних досить складно. Але можна відокремити задачу із змінною x1.

Після того як знайдено оптимальний розв’язок для першої підзадачі, виділяється підзадача з двома змінними x1 і x2, і вона розв’язується за допомогою вже знайденого розв’язку для першої задачі. Потім виділяється підзадача з трьома змінними x1, x2 і x3 і розв’язується за допомогою раніше використаного методу.

Важливо те, що у процесі розв’язування складної задачі не розв’язується заново чергова підзадача, а використовується вже отриманий розв’язок попередньої підзадачі. Наведемо типові задачі, які можна розв’язувати за допомогою динамічного програмування:

• розроблено граф доріг між населеними пунктами певного регіону; потрібно знайти мінімальний маршрут між двома населеними пунктами або маршрут, на який витрачається мінімальна кількість пального;

• корпорація виготовляє процесори, смартфони, монітори та інше обладнання; потрібно визначити оптимальну кількість виготовлення кожного виду пристроїв дляотримання максимального прибутку.

Розглянемо розв’язування задачі обчислення чисел Фібоначчі на прикладі 3.

Приклад 3. Нагадаємо, що числа Фібоначчі, починаючи з третього, отримують шляхом складання двох попередніх чисел, а перше і друге число дорівнюють одиниці: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...Щоб обчислити деяке число в цій послідовності, спочатку потрібно обчислити третє число, склавши перших два числа, потім четверте, склавши друге і третє числа, і т. д.

Нехай є сходи, по яких можна ступати по кожній сходинці або через одну. Скількома способами можна потрапити на i сходинку? На першу сходинку можна потрапити одним способом, на другу — двома, на третю — трьома способами.