Динамическое программирование

Dynamic Programming

Dynamic Programming

Для решение оптимизационных задач методами динамического программирования характерны два важных момента — меморизация и принцип оптимальности подзадач. Меморизация состоит в запоминании результатов решения подзадач, чтобы мгновенно решать их если они снова встретятся. Принцип оптимальности подзадач состоит в сведении исходной задачи к некоторому числу подзадач меньшей размерности. Обычно это продолжается до тех пор, пока решение не становится тривиальным. Обычно решение выражается некоторым рекуррентным математическим соотношением.

Знакомимся с теорией и разбираем эти задачи на базовые понятия.

Простые одномерные задачи:

Задачи среднего уровня сложности

Сложные задачи с динамикой по дереву

Выбираем и пытаемся также решить задачи на динамическаое программирование