Классические задачи динамического программирования

· Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

· Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

· Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.

· Задача о вычислении чисел Фибоначчи

· Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.

· Задача о выборе траектории

· Задача последовательного принятия решения

· Задача об использовании рабочей силы

· Задача управления запасами

· Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

· Алгоритм Флойда-Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

· Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

· Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами