Динамическое программирование
Введение ¶
Динамическое программирование (dynamic programming, DP) — мощный инструмент для решения определенного класса задач. Идея очень проста: если вы решили задачу для каких-то вводных данных, сохраните этот результат для будущих вычислений, чтобы снова не решать ту же самую задачу с теми же данными.
Запомните! «Кто не помнит своего прошлого, обречен на то, чтобы пережить его вновь»
Способы решения подобных задач ¶
-
Сверху-вниз: Начните с разбиения задачи на подзадачи. Если вы видите, что подзадача уже была решена, тогда используйте сохраненный ранее результат. Иначе решите подзадачу и сохраните её результат. Эта техника интуитивно понятна и называется мемоизацией.
-
Снизу-вверх: Проанализируйте задачу и определите порядок, в котором решаются подзадачи, и начните решать от тривиальной подзадачи до изначальной задачи. Это гарантирует, что подзадачи будут решены, прежде чем решится вся задача. В этом и заключается динамическое программирование.
Пример задачи динамического программирования ¶
В задаче по определению самой длинной возрастающей подпоследовательности необходимо найти найти самую длинную возрастающую подпоследовательность для заданной последовательности.
Для последовательности S={ a1, a2, a3, a4, ............., an-1, an } мы должны найти самое длинное подмножество, такое, что для всех j и i, j<i в подмножестве aj<ai.
Прежде всего, мы должны найти значение самых длинных подпоследовательностей (LSi) для каждого индекса i с последним элементом последовательности, равным ai. Тогда наибольшая LSi будет самой длинной подпоследовательностью в данной последовательности. Для начала LSi равна единице, поскольку ai является элементом последовательности (последний элемент). Затем для всех j таких, что j<i и aj<ai, мы находим наибольшую LSj и добавляем ее к LSi. Тогда алгоритм выполняется за O(n2).
Псевдокод для определения длины самой длинной возрастающей подпоследовательности:
сложность этого алгоритма можно уменьшить, если использовать структуру данных получше, а не массив. Использование массива с предшественниками и переменной largest_sequences_so_far («наибольшие последовательности на данный момент») и ее индекса сэкономит много времени.
Аналогичная концепция может быть применена для определения самого длинного пути в направленном ациклическом графе.
1for i=0 to n-1
2 LS[i]=1
3 for j=0 to i-1
4 if (a[i] > a[j] and LS[i]<LS[j])
5 LS[i] = LS[j]+1
6for i=0 to n-1
7 if (largest < LS[i])
Некоторые известные задачи DP ¶
- Floyd Warshall Algorithm - Tutorial and C Program source code
- Integer Knapsack Problem - Tutorial and C Program source code
- Longest Common Subsequence - Tutorial and C Program source code