Динамическое программирование

Нередко на олимпиадах встречаются задачи, провоцирующие использовать алгоритмы перебора. Но простой перебор может быть неоптимален, поэтому для решения таких задач используется метод динамического программирования. Этот метод заключается в разбиении сложной задачи на менее сложные подзадачи. Предполагается, что у нас есть таблица, куда мы запоминаем решения подзадач, при том, что нам известны самые начальные значения (например, нулевой элемент в таблице).

Самый яркий способ демонстрации работы метода динамического программирования – поиск $N$-ого числа в ряду Фибоначчи по заданному $N$.

Для справки: любое число в последовательности Фибоначчи $F$ – сумма двух предыдущих ему чисел в последовательности. $F_0 = 0$, $F_1 = 1$

Перед написанием кода выведем формулу нахождения $N$-ого числа Фибоначчи. Нетрудно понять, что $F_N = F_{N - 1} + F_{N – 2}$.

Таким образом решение можно представить в виде таблицы, где $i$-той ячейке преписывается решение задачи, в которой $N = i$.

$N$	0	1	2	3	4	5	$i$
$F_N$	0	1	1	2	3	5	$F_{i - 1} + F_{i – 2}$

Теперь запишем решение. В качестве таблицы будем использовать массив $M$ (от слова $Memory$), добавив в него два первых решения для двух первых значений $N$.

vector<int> M(N+1);
    M[0] = 0;
    M[1] = 1;

Обратите внимание, что $M$ имеет размер $N + 1$, чтобы после выполнения программы результат можно было найти по индексу $N$.

Далее напишем цикл, который пройдется по всей теблице и заполнит ее по выведенной формуле – M[i] = M[i-1] + M[i-2]. Ответом будет являться элемент $M_N$.

    for (int i=2; i<=N; ++i) {
        M[i] = M[i-1] + M[i-2];
    }
    cout << M[N] << '\n';

Сложность этого решения составляет $O(N)$.