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

нарізка java

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

Зміст

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

Що таке динамічне програмування (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, ми можемо ефективно обчислювати послідовність Фібоначчі без необхідності повторного обчислення підзадач.

порівняльний рядок у java

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

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

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

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

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

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

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

python новий рядок

приклад:

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

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

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

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

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

приклад:

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

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

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

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

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

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

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

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

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

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

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

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

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

підручник ssis

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

• Найдовша загальна підпослідовність (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 найпопулярніших питань для співбесіди з динамічного програмування
• «Практичні завдання» з динамічного програмування
• «Вікторина» з динамічного програмування