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

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

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

• Две цифры
• Три единицы
• Платформы
• Покупка билетов
• Платформы — 3
• Простая задачка Шарика
• Уменьшающееся число
• Ограбление домов
• Метеонаблюдения
• Кузнечик
• Лампионы
• Мышка и зёрнышки

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

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

• Вершинное покрытие
• Подсчет на дереве
• Максимальная сумма на дереве
• Покраска ребер
• Дерево
• Дерево
• Факторные деревья
• Расстояние в дереве
• Бинарное дерево
• n Div Дерево
• Микро и дерево

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

• Paint2D
• Paint2D-Crack
• Paint3D
• Конь и пешка
• Единицы
• Отрезки
• Две цифры
• Родственники
• Лесенка
• Конь и пешка против коня
• Слон и пешка против слона
• ACM
• Чернобыльський орёл на крыше
• Игра
• A-функция от строки
• Цирковое шоу
• Узор
• Игра с монетами
• Дом
• Простая задачка Шарика
• Простая задачка Печкина
• Банковская реформа
• Пчелиные соты
• Деление Гольдбаха

 

 

Related Images: