В чем заключается принцип оптимальности для подзадач при разработке алгоритмов?

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

Другими словами, решение задачи строится на оптимальных решениях подзадач. 2

Например, в задаче про черепашку любое начало оптимального пути до одной клетки будет оптимальным путём до некоторой другой клетки. 1

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