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

Определение

Оптимальная политика обладает тем свойством, что, каковы бы ни были начальное состояние и принятое начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, возникшего в результате первоначального решения.

Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)

[math]a \rightsquigarrow b \rightsquigarrow c [/math]

Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.