Одномерное ДП : кузнечик: различия между версиями
(Самая простая динамика) |
м |
||
Строка 17: | Строка 17: | ||
vector<int> dp(n, 0); | vector<int> dp(n, 0); | ||
for (int i = 1; i < n; i++) { | for (int i = 1; i < n; i++) { | ||
− | for (int j = max(0, i - 3) | + | for (int j = max(0, i - 3); j < i; j++) { |
dp[i] = max(dp[i], dp[j] + c[i]); | dp[i] = max(dp[i], dp[j] + c[i]); | ||
} | } | ||
Строка 24: | Строка 24: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Так | + | Так исторически сложилось, что чаще всего массив, где хранят значения динамики называют $dp$. |
===Общий план решения задачи на ДП=== | ===Общий план решения задачи на ДП=== |
Текущая версия на 13:00, 12 октября 2019
Эта статья дает базовое представление об идее динамического программирования.
Содержание
Кузнечик
Рассмотрим такую задачу: на прямой сидит кузнечик в точке $x = 0$, он умеет прыгать только вперед, причем только на расстояния $1$, $2$ или $3$. В каждой целой точке $i$ лежит $c_i$ монет. Кузнечику надо допрыгать до точки $x_f$, собрав как можно больше монет.
Посмотрим, откуда мог припрыгать кузнечик в точку $x_f$. Это либо $x_f - 1$, $x_f - 2$ либо $x_f - 3$. Допустим, мы как-то можем узнать оптимальный ответ, когда кузнечику надо дойти до каждой из этих точек. Назовем их $d_{1}, d_{2}, d_{3}$ соответственно. Это максимальное число монет, которое кузнечик может собрать на пути до каждой из точек. Тогда ответ для точки $x_f$ - это просто максимум из трех величин $d_1 + c_{x_f}$, $d_2 + c_{x_f}$, $d_3 + c_{x_f}$.
Задачу поиска оптимального ответа для $x_f$ свели к поиску ответа для меньших координат, то есть мы научились решать задачу, на основе каких-то ее подзадач. В этом и состоит основная идея динамического программирования.
Обыкновенно в задачах на ДП используют следующие термины:
- Состояние динамики - подзадачи, к которым мы можем свести исходную задачу;
- Переход - правило пересчета, то есть способ вычислить ответ на задачу с помощью ответов на подзадачи;
- База динамики - набор тривиальных состояний и значений для них. Например, в задаче про кузнечика ясно, что он может собрать $0$ монет по пути к точке $0$ (то есть не перемещаясь).
В простейших случаях ответы для состояний записывают в обычный массив. Например, решение задачи про кузнечика будет выглядеть так:
1 vector<int> dp(n, 0);
2 for (int i = 1; i < n; i++) {
3 for (int j = max(0, i - 3); j < i; j++) {
4 dp[i] = max(dp[i], dp[j] + c[i]);
5 }
6 }
7 cout << dp[n-1];
Так исторически сложилось, что чаще всего массив, где хранят значения динамики называют $dp$.
Общий план решения задачи на ДП
- Сформулировать, что будет значить состояние. Пример $dp[i]$ - максимальное число монет, которое можно собрать, дойдя до $i$;
- Определить формулу (формулы) пересчета динамики;
- Определить порядок, в котором будут считаться состояния динамики. Например, в данном случае нам надо было перебирать $i$ от $0$ до $n-1$, но в других задачах (например, в [двумерной динамике | Двумерная динамика]) этот порядок может быть менее тривиальным.
- Задать значения для тривиальных состояний;
- Понять, какое состояние соответствует ответу на всю задачу.
Восстановление ответа
Часто в задачах надо не только найти наибольшее или наименьшее значение чего-либо, но и сказать, как его получить. В задаче про кузнечика надо восстановить последовательность точек, по которым пропрыгает кузнечик. Рассмотрим два способа:
Запоминание ответа
Запомним в отдельный массив ту клетку, из который оптимальнее всего прыгнуть в текущую. Делаем это непосредственно при подсчете динамики. Массив $prev$ содержит лучшего предка.
1 vector<int> dp(n, 0);
2 for (int i = 1; i < n; i++) {
3 for (int j = max(0, i - 3): j < i; j++) {
4 if (dp[i] < dp[j] + c[i]) {
5 prev[i] = j;
6 dp[i] = dp[j] + c[i];
7 }
8 }
9 }
Затем надо пройтись от точки $n-1$ до нуля по построенному пути:
1 vector<int> path;
2 int cur = n - 1;
3 while (cur >= 0) {
4 path.push_back(cur);
5 cur = prev[cur];
6 }
Вопросы для внимательного читателя:
А теперь поймите, что такой код может уйти в бесконечный цикл. Как надо проинициализировать массив $prev$, чтобы избежать этого? В каком порядке будут идти точки в массиве $path$?
Повторный проход
Пусть мы уже посчитали массив динамики. Давайте пройдемся от последней точки к первой и будем по имеющимся значениям состояний определять, откуда мы пришли.
1 vector<int> path;
2 int cur = n - 1;
3 while (cur >= 0) {
4 path.push_back(cur);
5 if (cur >= 1 && dp[cur] == dp[cur - 1] + c[cur]) {
6 cur = cur - 1;
7 } else if (cur >= 2 && dp[cur] == dp[cur - 2] + c[cur]) {
8 cur = cur - 2;
9 } else if (cur >= 3 && dp[cur] == dp[cur - 3] + c[cur]) {
10 cur = cur - 3;
11 }
12 }
Плюс такого подхода в том, что не надо занимать лишнюю память для хранения предков для каждого состояния.
За сколько все работает
Значения динамики считаются в данном случае за один проход по массиву, ответ тоже можно восстановить за один проход, поэтому расход времени и памяти составит $O(n)$.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko