Изменения

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

Задача по нахождению кратчайшего пути до некоторой вершины между некоторыми вершинами графа (например, $S$_$i,j$) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$_$1,j-1$ или $S$_$2,j-2$). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием. ==Оптимальность для подзадач==Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:{{Определение|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}