Принцип динамического программирования при решении задач на оптимизацию пути в графе заключается в разбиении сложной задачи на несколько простых. 14

При этом на каждом шаге выбирается не лучшее решение, а то, которое предполагает максимальную сумму выигрыша от всех оставшихся шагов. 2

Некоторые особенности этого принципа:

• Вычисления проводятся дважды: сначала от конца к началу (определение условно-оптимального решения), затем от начала к концу (определение безусловно-оптимального решения). 2
• Важнейшее свойство задач — оптимальность для подзадач. 3 Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом. 3