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

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

Дп применяется для нахождения оптимального решения, или для подсчёта способов решения.

Для того чтобы решить задачу с помощью ДП, надо разобраться с :

1. какие состояния
2. начальные значения, некоторых состояний
3. пересчёт новых состояний из ранее посчитанных состояний, не обязательно по порядку
4. состояния где ответ

Более подробнее :

1. Состояния обычно одномерные или двумерные. Например, сколько первых элементов массива мы рассматриваем, или начало и конец рассматриваемого отрезка. Могут быть и более многомерные случае.

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

3. Новые состояния пересчитываются из учёта значений уже посчитанных состояний. Если придумать правильные состояния и пересчёт их то можно считать что задача уже решена.

4. Состояния в которых хранится ответ легко определить из структуры состояний. Скорее всего, ответ это значение в самом последнем слое — dp[n] или max(dp[n][i]) для всех i от 1 до n.

Числа Фибоначчи

Рассмотрим задачу, посчитать $n$-ое значение ряда Фибоначчи.

$0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,\dots$

Решение рекурсией

Можно написать рекурсивную функцию для вычисления $n$-го числа, которая работает за $O(2^n)$:

int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Решение динамическим программированием

По пунктам :

1. Состояния $i$ — $i$-ое число Фибоначчи.
2. Начальное значение будет только у первых двух членов последовательности $f_0=0,f_1=1$
3. Пересчёт $i$-го состояния следует из определения — $f_i=f_{i-1}+f_{i-2}$
4. Ответ на задачу будет $n$-ое состояние.

Нерекурсивный способ

Иногда значения можно пересчитать по порядку. Например, как в этой задаче.

int fib[n + 1];

fib[0] = 0;
fib[1] = 0;
for (int i = 2; i <= n; i++) {
	fib[i] = fib[i - 1] + fib[i - 2];
}
cout << fib[n];

Рекурсивный способ

Такой способ ещё называется ленивой динамикой (или мемонизацией). Иногда сложно или вообще невозможно придумать порядок пересчёта динамики, что все необходимые значения уже посчитаны.

std::vector<int> f(MAX_N, -1);

int fib(int n)
{
 if (f[n] != -1) { // +
   return f[n]; // +
 } // +

 if (n <= 1)
   return n;
 return f[n] = fib(n - 1) + fib(n - 2); // добавили кэширование значения
}

Условие f[n] != -1 проверяет на то, что значение уже было посчитано. Получается асимптотика $O(n)$

Комбинаторные задачи

Почти все (хотя пока я писал, я нашёл обратное, видимо, все не комбинаторные задачи запомнились больше) задачи сформулированы так : посчитайте количество ... по простому модулю.

Так как значения ДП, равны или сумме значений или вообще умножаются на что-то, следовательно значения не вмещаются в нормальные целочисленные типы.

Поэтому надо написать пару функций, для поддерживания значений по модулю.

const int MOD = 1e9 + 7;

inline int add(const int &a, const int &b) { // a + b
    return (a + b >= MOD) ? a + b - MOD : a + b;
}

inline int sub(const int &a, const int &b) { // a - b
    return (a - b < 0) ? a - b + MOD : a - b;
}

inline int mult(const int &a, const int &b) { // a * b
    return (1LL * a * b) % MOD;
}

Восстановление ответа

Очень редко просят восстановить ответ.

Для этого храним дополнительно массив, в котором храним состояние откуда через которое мы обновили текущее состояние, при пересчёте.

Пример, (на самом деле таких задач много, мне просто лень) :

Цветная полоска

Найди Число

Виды динимики

По подотрезкам По цифрам По подмноджествам По поддеревьям

Тупо покидаю ссылки :

1. Динамика по подотрезкам
2. Ленивая динамика
3. Динамика по цифрам
4. (en) Введение в ДП
5. (en) Аналогично Всё о рюкзаке, и задачи похожие
6. (en) Аналогично Пути на сетке
7. (en) Аналогично НВП
8. (en) Аналогично Подмаски
9. (en) Аналогично подотрезки
10. (en) Аналогично По цифрам
11. (en) Аналогично По поддеревьям + ещё там есть рерутинг

в 4-11 реально крутой сайт, задачи данные внизу очень крутые.

Задачи :

1. просто посмотрите самые простые задачи на динамику на кф'е (там разбор есть) я не знаю как сказать, но там как раз половина задач самых простых не динамика, или это немного сложнее чем другие решения
2. специальный контект на динамику (есть самые базовые) (есть сотни разборов)
3. секция Dynamic Programming 20+задач (есть самые базовые)
4. какие-то задачи

Давайте рассмотрю пару :

• Между Двумя Массивами
• Общие Подпоследовательности
• Цветные Кирпичики
• Переупорядочивание
• Отсортирована?
• Цветная Полоска
• Красное И Синее Дерево
• Хорошая Бинарная Матрица
• Квадратные Подмножества
• Совместимые Числа