Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать.
Рассмотрим такую задачу: требуется найти $n$-ое число Фибоначчи $f_n$, определяемое как
$$ \begin{aligned} f_0 &= 0 \\ f_1 &= 1 \\ f_n &= f_{n-2} + f_{n-1} \end{aligned} $$Записав определение выше как функцию, задачу можно решить рекурсивно:
int f(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return f(n - 2) + f(n - 1);
}
Однако для $n$, превосходящих ~40, такое решение будет работать очень долго. Попытаемся грубо оценить время работы $T(n)$.
Чтобы посчитать $f_n$, нам нужно рекурсивно посчитать $f_{n-1}$ и $f_{n-2}$:
$$ T(n) = T(n-2) + T(n-1) + \Theta(1) $$ Для подсчета $f_{n-1}$ нужно не меньше действий, чем для $f_{n-2}$. Объединяя с предыдущим, это значит, что $f_n$ нужно хотя бы в два раза больше действий, чем для $f_{n-2}$: $$ T(n) \ge 2 \cdot T(n-2) $$ А значит, время работы растет экспоненциально: $$ T(n) \ge \Omega(2^{n/2}) $$Упражнение. Какое точное суммарное количество рекурсивных вызовов будет при подсчете $f_n$?
Запоминание результатов
Основная идея — сводить задачу к меньшим, и в какой-то момент к базовым — совершенно правильная.
Однако нужно следить за тем, чтобы число этих задач не росло экспоненциально. Для этого проще всего не совершать никаких лишних действий: если мы один раз посчитали $f_n$, то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, будем использовать его сразу.
Удобнее всего завести массив для всех нужных значений $f_n$ и, вместо рекурсивной функции, инициализировать его базовые значения, а затем пройтись в цикле по всем остальным $f_i$ и посчитать их, используя уже известные после предыдущих итераций $f_{i-2}$ и $f_{i-1}$:
const int n = 100;
int f[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; i++)
f[i] = f[i - 2] + f[i - 1];
(Для больших $n$ в последней строчке будет происходить переполнение, поэтому часто в подобных задачах все значения рассматривают по модулю.)
Динамическим программированием (англ. dynamic programming, ДП, динамика) называется как раз приведенный выше подход, обычно заключающийся в следующих общих шагах:
- Свести задачу для $n$ к задаче для чисел, меньших, чем $n$ — то есть найти какую-то рекурсивную формулу.
- Создать массив (или какую-нибудь другую структуру данных) для хранения ответов на подзадачи.
- Заполнить начало массива вручную (базовые случае, для которых формула не работает).
- Обойти массив от известных значений в неизвестные и заполнить ответы по формуле.
- Вывести ответ — обычно просто записанный в последней ячейке массиве.
Чтобы решить задачу динамическим программированием, вы должны ответить на 5 вопросов:
- Что лежит в массиве? (чаще всего самый важный вопрос)
- Как инициализировать начало массива?
- Как обходить массив? (чаще всего слева направо, но не всегда)
- Какой формулой считать элементы массива?
- Где в массиве лежит ответ?
Этим приемом можно решать большое количество важных задач, и в этом разделе мы в этом убедимся.