Суть метода динамического программирования. Вычисление последовательности Фибоначчи. Задача поиска наибольшей увеличивающейся подпоследовательности. Расстояние Левенштейна. Порядок перемножения матриц. Алгоритмы Флойда-Уоршелла и Беллмана-Форда.
Аннотация к работе
Ставится вопрос: как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным? Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, предшествующей ей. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово программирование в словосочетании динамическое программирование в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании математическое программирование, которое является синонимом слова оптимизация. Поэтому слово программа в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи.