Одномерное ДП : кузнечик

Материал из Algocode wiki
Перейти к: навигация, поиск

Эта статья дает базовое представление об идее динамического программирования.

Кузнечик

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