Общие приёмы динамики

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать.

Рассмотрим такую задачу: требуется найти $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 вопросов:

Что лежит в массиве? (чаще всего самый важный вопрос)
Как инициализировать начало массива?
Как обходить массив? (чаще всего слева направо, но не всегда)
Какой формулой считать элементы массива?
Где в массиве лежит ответ?

Этим приемом можно решать большое количество важных задач, и в этом разделе мы в этом убедимся.