В чем заключается метод динамического программирования при решении олимпиадных задач?

Метод динамического программирования при решении олимпиадных задач заключается в разбиении сложной задачи на менее сложные подзадачи. 4

Ключевая идея: решить отдельные части задачи (подзадачи), после чего объединить их решения в одно общее. 1 Часто многие из этих подзадач одинаковы. 1 Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. 1

Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. 3

Некоторые типы олимпиадных задач, для которых применяют метод динамического программирования:

• Задача о рюкзаке. 2 Есть набор предметов с весами и стоимостями, нужно выбрать такие предметы, чтобы их общий вес не превышал заданного предела, а общая стоимость была максимальной. 2
• Задачи на потоки. 2 Включают в себя нахождение максимального потока в сети, потока минимальной стоимости и т. д.. 2
• Задачи о перекрывающихся подмножествах. 2 Нужно найти минимальное количество подмножеств, которые покрывают все элементы данного множества. 2
• Задачи об оптимальном пути. 2 Включают в себя задачи о лабиринтах, нахождение кратчайшего пути в графе и т. п.. 2
• Задачи коммивояжёра. 2 В этих задачах коммивояжёр должен посетить все города, вернувшись в исходный, найдя при этом оптимальный маршрут. 2
• Задачи о разбиении. 2 Здесь требуется найти такое разбиение числа на слагаемые, чтобы их сумма была наименьшей или наибольшей. 2