ДП находит оптим решение n-мерной задачи путем декомпозиции на n этапов, каждый из котор сосотав задачу от 1 переменной. Эти задачи долж быть связаны между собой общим условием. Вычисления выполняются рекурентно. Решени первой подзадачи явл иходными данными для 2-й. Решив последнюю получим оптим решение.Для решения задач динамического программирования необходимо выполнить сле-дующие действия: 1. Определить этапы. 2. Определить на каждом этапе вариантов решения (альтернатив). 3. Определить состояния на каждом этапе. 4. Рекурентная формулаДва метода: прямой и обрат прогонки.Рекурентные вычисления производятся от начьной вершины до конченой, а выписывание оптимального реения проиходит в обранном порядке.Как привило в задачах ДП используется алгоритм обратной погонки.Постановка задачи динамического программирования