Алгоритмы и структуры данных. Лекция 6

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

• Предварительные сведения: ациклические ориентированные графы.
• Общие принципы динамического программирования, часто используемые подзадачи.
• Кратчайшие пути в ациклических ориентированных графах.
• Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности.
• Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе.