285
правок
Изменения
Нет описания правки
==Оптимальная подструктура==
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
Задача по нахождению кратчайшего пути до некоторой вершины графа (например, $S$<sub>$i,j$</sub>) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$<sub>$1,j-1$</sub> или $S$<sub>$2,j-2$</sub>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
