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

Введение

Динамическое программирование (ДП) — это подход к решению проблем, заключающийся в применении стратегии:

1. Разбиение проблемы на подпроблемы.
2. Решение подпроблем.
3. Сборка решений подпроблем в решение исходной проблемы.

Область применения

ДП позволяет за полиномиальное время решить проблемы, обладающие, казалось бы, экспоненциальной сложностью. Это проблемы относящиеся к двум основным классам:

• комбинаторные задачи — сколькими способами можно замостить участок пола квадратными плитками разных размеров.
• задачи оптимизации - собрать наиболее ценные для похода вещи в ограниченный рюкзак.

Критерии выбора ДП в качестве метода решения

Чтобы быть эффективно решаемой методом ДП проблема должна обладать свойствами:

• Optimal substructure - отпимальное решение проблемы может быть построено из оптимального решения подпроблем.
• Overlapping subproblems - для решения подпроблем используются результаты уже решённых подпроблем.
• Acyclic dependencies (?) - решения любых двух подпроблем не могут зависеть друг от друга.

Если эти свойства не выполняются, то задача либо решается быстрее/оптимальнее жадным алгоритмом, либо не решается методом ДП вовсе.

Причём тут графы

В конечном итоге ДП — это обход некоторого DAG'a:

• в задачах оптимизации нужно обойти граф по минимальной/максимальной цене.
• в комбинаторных задачах — посчитать количество рёбер/вершин.

Фреймворк

Чтобы применить к проблеме метод ДП, нужно выполнить 5 "простых" шагов:

1. Определить подпроблемы.
2. Предположить часть решения.
3. Соотнести решения подпроблем друг с другом.
4. Построить алгоритм: сверху-вниз (рекурсия) или снизу-вверх (таблица значений).
5. Убедиться, что исходная проблема решена.

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

Остальная часть решения практически идентичная для всех ДП задач.