285
правок
Изменения
Нет описания правки
<wikitex>
==Определение==
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так:
{{Определение
|definition = '''Принцип оптимальности для подзадач''' – важнейшее свойство задачи, формулирующееся следующим образом: «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}==Принцип оптимальности для динамического программирования на префиксе==
Рассмотрим принцип оптимальности для динамического программирования на префиксе:
