Основи динамічного програмування


Рівень складності Легко
Часто запитують у Infosys MAQ
Динамічне програмування теорія

У Основах динамічного програмування ми розглянемо основи ДП та її відмінності від методу Жадібного, Розділяй і підкорюй та Рекурсія.

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

Він використовується для оптимізації програм. Оскільки він використовує обчислені раніше результати, використання його експоненціальної часової складності може бути зведено до полінома. Наприклад - Часова складність рекурсивного розв’язку Потворних Чисел є експоненціальною, а розв’язку DP - лінійною.

Деякі основні проблеми ДП

  • Проблема потворних чисел
  • Заміна монети
  • Числа Фібоначчі
  • Проблема чисел дзвона
  • Вежа Ханоя
  • Дзвонні номери
  • Проблема з рюкзаком

Динамічне програмування (DP) проти Жадібного методу

У DP кожен крок оцінює рішення, враховуючи поточне, а також попередні рішення, щоб отримати оптимальне рішення. Однак у жадібному алгоритмі ми вибираємо найкращий варіант, враховуючи лише поточну ситуацію.

Хоча жадібні методи, як правило, швидші, ніж DP, а також ефективні для пам'яті, оскільки не зберігають раніше обчислені значення для подальшого використання, вони не дають гарантії оптимального рішення.

Динамічне програмування (DP) проти методу Divide & Conquer

У розділі та підкоренні ми ділимо задачу на підзадачі та вирішуємо кожну підзадачу самостійно. Однак у DP, а не самостійно вирішувати задачі, ми використовуємо отримані раніше результати для нових обчислень. Іншими словами, ми можемо сказати Divide and Conquer + Memoization = динамічний підхід зверху вниз.

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

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

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

Рекурсія призводить до перерахунку задач кілька разів, тому в таких випадках складність рекурсії завжди більша, ніж рішення DP.

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

Посилання Питання інтерв'ю