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

Динамічне програмування

Зміст

• Що таке динамічне програмування?
• Як працює динамічне програмування?
• Приклади динамічного програмування
• Коли використовувати динамічне програмування?
• Підходи динамічного програмування
• Алгоритм динамічного програмування
• Переваги динамічного програмування
• Застосування динамічного програмування
• Вивчіть основи динамічного програмування
• Розширені концепції динамічного програмування
• Задачі динамічного програмування

Що таке динамічне програмування (DP)?

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

Як працює динамічне програмування (DP)?

• Визначте підпроблеми: Розділіть основну проблему на менші незалежні підпроблеми.
• Магазин Рішення: Розв’яжіть кожну підзадачу та збережіть розв’язок у таблиці чи масиві.
• Рішення для нарощування: Використовуйте збережені рішення для створення рішення основної проблеми.
• Уникайте надмірності: Зберігаючи рішення, DP гарантує, що кожна підпроблема вирішується лише один раз, зменшуючи час обчислення.

Приклади динамічного програмування (DP)

приклад 1: Розглянемо задачу знаходження послідовності Фібоначчі:

Послідовність Фібоначчі: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Підхід грубої сили:

Щоб знайти n-е число Фібоначчі за допомогою підходу грубої сили, потрібно просто додати (n-1)-й і (n-2)-й Числа Фібоначчі. Це спрацювало б, але було б неефективно для великих значень п , оскільки це вимагало б обчислення всіх попередніх чисел Фібоначчі.

Підхід динамічного програмування:

Ряд Фібоначчі з використанням динамічного програмування

• Підпроблеми: F(0), F(1), F(2), F(3), …
• Магазин Рішення: Створіть таблицю для зберігання значень F(n) під час їх обчислення.
• Рішення для нарощування: Для F(n) знайдіть F(n-1) і F(n-2) у таблиці та додайте їх.
• Уникайте надмірності: Таблиця гарантує, що кожна підзадача (наприклад, F(2)) буде розв’язана лише один раз.

Використовуючи DP, ми можемо ефективно обчислювати послідовність Фібоначчі без необхідності повторного обчислення підзадач.

приклад 2: Найдовша спільна підпослідовність (пошук найдовшої підпослідовності, спільної для двох рядків)

приклад 3: Найкоротший шлях у графі (пошук найкоротшого шляху між двома вузлами в графі)

Приклад 4: Задача про рюкзак (знаходження максимальної вартості предметів, які можна помістити в рюкзак заданої місткості)

Коли використовувати динамічне програмування (DP)?

Динамічне програмування - це техніка оптимізації, яка використовується при розв'язанні задач і складається з наступних характеристик:

1. Оптимальна підструктура:

Оптимальна підструктура означає, що ми поєднуємо оптимальні результати підпроблем для досягнення оптимального результату більшої проблеми.

приклад:

Розглянемо задачу на знаходження мінімальна вартість шлях у зваженому графі від a джерело вузол до a призначення вузол. Ми можемо розбити цю проблему на менші підпроблеми:

• Знайди мінімум вартість шлях від ст джерело вузол для кожного проміжний вузол.
• Знайди мінімум вартість шляху від кожного проміжний вузол до призначення вузол.

Рішення більшої проблеми (знаходження шляху з мінімальною вартістю від вихідного вузла до вузла призначення) можна побудувати з рішень цих менших підпроблем.

2. Перекриваються підпроблеми:

Одні і ті ж підзадачі вирішуються неодноразово в різних частинах задачі.

приклад:

Розглянемо задачу обчислення Ряд Фібоначчі . Щоб обчислити число Фібоначчі за індексом п , нам потрібно обчислити числа Фібоначчі за індексами n-1 і n-2 . Це означає, що підзадача обчислення числа Фібоначчі за індексом n-1 використовується двічі у вирішенні більшої проблеми обчислення числа Фібоначчі за індексом п .

Підходи динамічного програмування (DP)

Динамічного програмування можна досягти за допомогою двох підходів:

1. Підхід «зверху вниз» (запам’ятовування):

У підході зверху вниз, також відомому як запам'ятовування , ми починаємо з остаточного рішення і рекурсивно розбиваємо його на менші підпроблеми. Щоб уникнути зайвих обчислень, ми зберігаємо результати розв’язаних підзадач у таблиці запам’ятовування.

Давайте розберемо підхід зверху вниз:

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

2. Підхід «знизу вгору» (табулювання):

Підхід «знизу вгору», також відомий як табулювання , ми починаємо з найменших підпроблем і поступово доводимо до остаточного рішення. Ми зберігаємо результати розв’язаних підзадач у таблиці, щоб уникнути зайвих обчислень.

Давайте розберемо підхід «знизу вгору»:

• Починається з найменших підпроблем і поступово доходить до остаточного рішення.
• Заповнює таблицю рішеннями підзадач у порядку «знизу вгору».
• Підходить, коли кількість підпроблем невелика, а оптимальне рішення можна безпосередньо обчислити з розв’язків менших підпроблем.

Динамічне програмування (DP) Алгоритм

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

Загальні алгоритми, які використовують динамічне програмування:

• Найдовша загальна підпослідовність (LCS): Знаходить найдовшу спільну підпослідовність між двома рядками.
• Найкоротший шлях у графіку: Знаходить найкоротший шлях між двома вузлами на графі.
• Проблема з ранцем: Визначає максимальну вартість предметів, які можна помістити в рюкзак заданої місткості.
• Ланцюгове множення матриць: Оптимізує порядок множення матриць, щоб мінімізувати кількість операцій.
• Послідовність Фібоначчі: Обчислює n-е число Фібоначчі.

Переваги динамічного програмування (DP)

Динамічне програмування має ряд переваг, зокрема:

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

Застосування динамічного програмування (DP)

Динамічне програмування має широкий спектр застосувань, зокрема:

• Оптимізація: Проблема ранця, задача найкоротшого шляху, задача максимального підмасиву
• Комп'ютерна наука: Найдовша спільна підпослідовність, відстань редагування, відповідність рядків
• Дослідження операцій: Управління запасами, планування, розподіл ресурсів

Тепер давайте розглянемо вичерпну дорожню карту для опанування динамічного програмування.

Вивчіть основи динамічного програмування (DP)

• Що таке мемоізація? Повний підручник
• Табуляція проти мемоізації
• Оптимальна властивість субструктури
• Властивість підпроблем, що перекриваються
• Як вирішити задачу динамічного програмування?

• Числа Фібоначчі
• n-те каталонське число
• Номери дзвоників (кількість способів розділити набір)
• Біноміальний коефіцієнт
• Проблема розміни монет
• Проблема суми підмножини
• Обчисліть nCr % p
• Нарізка стрижня
• Алгоритм фарбування паркану
• Найдовша загальна підпослідовність
• Найдовша зростаюча підпослідовність
• Найдовша підпослідовність така, що різниця між сусідніми дорівнює одиниці
• Квадратна підматриця максимального розміру з усіма одиницями
• Шлях мінімальної вартості
• Мінімальна кількість стрибків, щоб досягти кінця
• Найдовший загальний підрядок (розчин DP, оптимізований за простором)
• Порахуйте шляхи досягнення n-ої сходинки, використовуючи крок 1, 2 або 3
• Підрахуйте всі можливі шляхи від верхнього лівого до нижнього правого кута матриці mXn
• Унікальні шляхи в сітці з перешкодами

2. Середні задачі з динамічного програмування (DP)

• Алгоритм Флойда Воршелла
• Алгоритм Беллмана–Форда
• 0-1 Проблема ранця
• Друк предметів у рюкзаку 0/1
• Необмежений рюкзак (дозволено повторення предметів)
• Головоломка падіння яйця
• Проблема розриву слів
• Проблема покриття вершини
• Проблема укладання плитки
• Проблема укладання ящиків
• Проблема розділу
• Задача комівояжера | Набір 1 (Наївне та динамічне програмування)
• Найдовша паліндромна підпослідовність
• Найдовша загальна зростаюча підпослідовність (LCS + LIS)
• Знайти всі окремі суми підмножини (або підпослідовності) масиву
• Зважений графік роботи
• Порушення підрахунку (перестановка так, що жоден елемент не з’являється у своїй початковій позиції)
• Мінімум вставок для формування паліндрому
• Зіставлення шаблону підстановки
• Способи розташування куль таким чином, щоб сусідні кулі були різних типів

3. Складні задачі з динамічного програмування (DP)

• Паліндромне розбиття
• Проблема переносу слів
• Проблема перегородки художника
• Програма для проблеми моста і факела
• Ланцюгове множення матриць
• Друк дужок у задачі ланцюгового множення матриць
• Прямокутник із максимальною сумою у двовимірній матриці
• Максимальний прибуток при купівлі та продажу акції не більше k разів
• Мінімальна вартість сортування рядків за допомогою операцій розвороту різних витрат
• Кількість підпослідовностей AP (арифметичної прогресії) в масиві
• Введення в динамічне програмування на деревах
• Максимальна висота дерева, коли будь-який вузол можна вважати коренем
• Найдовший підрядок, що повторюється та не перекривається

Швидкі посилання:

• Вивчіть структуру даних і алгоритми | Підручник DSA
• 20 найпопулярніших питань для співбесіди з динамічного програмування
• «Практичні завдання» з динамічного програмування
• «Вікторина» з динамічного програмування