Изучите базовые концепции динамического программирования
Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.
Дана таблица из строк и столбцов. В каждой ячейке , где , , находится монеток.
В левом верхнем углу стоит черепашка, то есть в ячейке . Черепашка может двигаться только вниз или направо. Черепашке нужно дойти до ячейки , собрав максимальное количество монет.
Как решить данную задачу? Давайте сначала попробуем решить её с помощью рекурсии.
Обозначим через максимальное количество монет, которое может собрать черепашка, если она стартует из и дойдёт до клетки . Тогда ответом будет .
Вернёмся теперь к динамическому программированию. Принцип динамики очень похож на принцип рекурсии.
Вспомним, что такое динамика: динамическое программирование — это способ решения задачи путём разбиения её на более простые подзадачи.
Именно это мы делали выше. Для нахождения ответа (при или ) мы вычисляли значения более простых задач — и .
В этом случае:
Обычно при решении задач динамического программирования придерживаются следующей логики:
Возникает вопрос: в чём тогда разница между динамическим программированием и рекурсивным перебором?
В обоих случаях у нас есть состояния и переходы между ними.
Разница заключается в том, что в динамическом программировании одни и те же состояния не вычисляются несколько раз, тогда как в обычной рекурсии они могут вычисляться многократно.
Вспомним урок по рекурсии с запоминанием (memoization), где мы разбирали, почему рекурсия может пересчитывать одни и те же значения и как эту проблему решить.
Ту же самую идею можно применить и здесь. Если добавить запоминание в рекурсивное решение, то мы фактически получим решение с использованием динамического программирования.
Черепашка нашла массив из чисел. Черепашке нужно выбрать некоторое подмножество этих чисел так, чтобы их сумма была максимальной среди всех возможных вариантов.
Однако есть ограничение: нельзя выбирать два соседних числа одновременно.
Как решить эту задачу?
Найдём состояния динамики. Пусть — максимальная сумма, которую черепашка может собрать, используя только элементы префикса длины .
То есть рассматриваем массив .
Базовые случаи:
Теперь рассмотрим, как вычислить при . Возможны два варианта:
Черепашка берёт число на позиции .
Тогда она не может взять , поэтому может использовать только префикс
.
Сумма в этом случае равна .
В итоге получаем формулу динамики:
Ответом на исходную задачу будет значение .
Черепашка не берёт число на позиции .
Тогда она может использовать префикс
, а сумма равна .
int Rec(int x, int y) {
if (x == 1 && y == 1) {
return C[1][1];
} else {
int best = 0;
if (x > 1) {
best = max(best, Rec(x - 1, y));
}
if (y > 1) {
best = max(best, Rec(x, y - 1));
}
return best + C[x][y];
}
}
map<pair<int, int>, int> mem;
int Rec(int x, int y) {
if (x == 1 && y == 1) {
return C[1][1];
} else {
if (mem.find({x, y}) != mem.end()) {
return mem[{x, y}];
}
int best = 0;
if (x > 1) {
best = max(best, Rec(x - 1, y));
}
if (y > 1) {
best = max(best, Rec(x, y - 1));
}
return mem[{x, y}] = best + C[x][y];
}
}
dp[0] = 0;
dp[1] = a[1];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 2] + a[i], dp[i - 1]);
}