# Разбор задач на динамическое программирование
[ToC]
## Общая терминология
:::info
В целом сейчас все термины объясняются по мере их появления в разборах, но если надо будет, вынесу термины отдельно сюда
:::
## B. Кузнечик-K
Рассмотрим $d_i$ -- решение задачи следующего вида:
> [color=green] [name=Задача "$i$"] У кузнечика есть $i+1$ столбик с номерами $0..i$.
> За один шаг кузнечик может прыгнуть на $1..k$ столбиков вперед.
> Сколькими способами он может допрыгать с $0$-го столбика до $i$-го?
Заметим, что $$d_0 = 1$$ потому что есть единственный способ никуда не двигаться -- не совершать никаких прыжков.
Рассмотрим $i > 0$, и посмотрим на последний сделанный кузнечиком прыжок. Поскольку он был длиной от $1$ до $k$, начинаться он мог в $k$ предшествующих столбиках.
Ключевое наблюдение: каждый способ добраться до столбика $i-j$ (где $j \in 1..k$) однозначно соответствует какому-то способу добраться до $i$, сделав последний прыжок длиной ровно $j$. Поэтому все способы, входящие в число $d_i$, состоят из
- $d_{i-1}$ способов добраться до $i-1$ и сделать прыжок длины $1$
- $d_{i-2}$ способов добраться до $i-2$ и сделать прыжок длины $2$
...
- $d_{i-k}$ способов добраться до $i-k$ и сделать прыжок длины $k$
Разумеется, также стоит не забывать, что для $i < k$ эта последовательность будет ограничена $d_0$, так как отрицательных столбиков не бывает.
На основе этих наблюдений можно написать следующий код:
```cpp
unsigned int n, k;
cin >> n >> k;
vector<int> d(n, 0);
d[0] = 1;
for (unsigned int i = 1; i < n; i++) {
for (unsigned int j = 1; j <= k && j <= i; j++) {
d[i] += d[i - j];
}
}
cout << d[n - 1];
// так как нумерация в условии с 1, а у нас с 0, то индекс ответа n - 1
```
<span style="color:red">Улучшенное решение</span> (ускоряющее код примерно в $k$ раз):
- заметим, что на самом деле нам не обязательно каждый раз считать сумму $k$ последних $d_{i-j}$ заново
- в тот момент, когда мы считаем $d_{i-1}$, мы считаем сумму $$d_{i-1-k} + ... + d_{i-2}$$
- чтобы получить сумму $k$ ответов, предшествующих $i$, достаточно вычесть $d_{i-1-k}$ и прибавить $d_{i-1}$
```cpp
unsigned int n, k;
cin >> n >> k;
vector<int> d(n, 0);
d[0] = 1;
long long result = 0; // запоминаем сумму
for (unsigned int i = 1; i < n; i++) {
result += d[i - 1];
if (i > k) result -= d[i - k - 1];
// пересчитали сумму, теперь знаем ответ
d[i] = result;
}
cout << d[n - 1];
```
## C. Кузнечик собирает монеты
Идея аналогичная, но в этот раз мы вместо подсчета числа способов, ищем оптимальный способ. Основная сложность этой задачи -- **восстановление ответа**. В задачах на поиск оптимального ответа часто бывает нужно вывести не только сам результат, но и способ его получить. В данном случае результат -- число монет, а способ -- конкретный путь от первого столбца до последнего.
Сначала в голову может прийти идея для каждого **состояния динамики** (состояние -- набор переменных, описывающих задачу; в прошлой задаче эту роль играло $i$) хранить оптимальный путь, которым можно в него прийти. К сожалению, часто такой подход либо неверен, либо просто требует больших затрат по времени и памяти.
Для решения этой проблемы можно сделать следующее наблюдение: нам не обязательно знать весь путь, которым мы шли до конца, если для каждого состояния пути мы знаем, откуда мы в него пришли. Например, для пути $$1 \rightarrow 2 \rightarrow 5 \rightarrow 7$$ нам достаточно знать, что $$p_2 = 1, p_5 = 2, p_7 = 5$$ где $p_i$ -- номер столбика, из которого надо прыгать в $i$, чтобы получить оптимальный результат.
С учетом этого, формулируем нашу динамическую задачу для состояния $i$ следующим образом:
> [color=green] [name=Задача "$i$"] У кузнечика есть $i+1$ столбик с номерами $0..i$. Для $j$-го столбика известно $c_j$ -- число монет, которое кузнечик получает после прыжка на него. Считаем также, что $c_0 = c_i = 0$.
> За один шаг кузнечик может прыгнуть на $1..k$ столбиков вперед.
> **Решение задачи** -- $(d_{0..i}, p_{0..i})$, где $d_j$ -- это максимальное число монет, которым можно обладать, находясь на $j$-м столбике, а $p_j$ -- прошлое перед $j$ состояние, из которого надо делать прыжок, чтобы после прыжка иметь ровно $d_j$ монет.
Посмотрим, по каким правилам определяются наши $d_i$ и $p_i$. Заметим, что $$d_0 = 0$$ так как находясь в нулевом столбике, можно иметь только $0$ монет. Обозначим $p_0 = -1$ просто для удобства написания кода, оно не будет иметь никакого практического смысла.
Теперь рассмотрим $i > 0$, и все возможные предыдущие состояния. Процесс прыжка на $i$-й столбик завершается прибавлением к сумме монет $c_i$. Поэтому, чтобы получить максимальную сумму в результате, надо начинать прыжок с макисмальным возможным числом монет.
Из этого наблюдения можно понять, что
- $p_i = \mathtt{argmax}_{j=1..k} d_{i-j}$, то есть $p_i = j$ из интервала $1..k$, такому, что $d_{i-j}$ максимально
- $d_i = d_{p_i} + c_i$
Последняя задача заключается в том, чтобы зная все $p_j$, уметь восстанавливать весь путь. Ну пусть $t = p_i$. Тогда из какого состояния мы пришли в $t$? Это $p_t$, то есть $p_{p_i}$. В свою очередь, прошлое перед ним -- это $p_{p_{p_i}}$, и так далее. Чтобы понять, в какой момент эта цепочка останавливается, мы приравняли $p_0$ к $-1$, чтобы выйти из этого цикла, когда дойдем до $-1$.
Теперь можно написать код (в две части -- поиск и восстановление ответа):
```cpp
unsigned int n, k;
cin >> n >> k;
vector<int> c(n, 0);
for (unsigned int i = 1; i < n - 1; i++) {
cin >> c[i];
}
vector<int> d(n, 0), p(n, -1);
for (unsigned int i = 1; i < n; i++) {
for (unsigned int j = 1; j <= k && j <= i; j++) {
// если нашли ответ лучше, или вообще еще не нашли
if (d[i] < d[i - j] || p[i] == -1) {
d[i] = d[i - j];
p[i] = i - j;
}
d[i] += c[i];
}
}
cout << d[n - 1] << '\n';
```
```cpp
int last = n - 1;
vector<int> path;
while (last != -1) {
path.push_back(last);
last = p[last];
}
// не забыть #include <algorithm>
// поскольку вершины добавляются начиная с последней, надо развернуть
reverse(path.begin(), path.end());
for (int i : path) {
cout << i + 1 << ' ';
}
```
Аналогично первой, в этой задаче есть <span style="color:red">улучшенное решение</span>, код которого не приводится, потому что его можно написать аналогично задаче [1B](#1B-Кузнечик-K). Поскольку его суть в поиске максимума не за $\mathcal{O}(k)$, а за $\mathcal{O}(\log{k})$, можно применить
- дерево отрезков
- ~~Sparse Table~~ (мы только мельком касались этой темы, не страшно, если никогда не слышали о таком)
- обычный `std::set`, который, наверное, будет самым простым решением
## D. Последовательность из 0 и 1
Типичный и более сложный вид динамики -- в котором **состояние** описывается не только числами, которое программа получает на вход (в задачах про кузнечика на вход подавалось $n$, и мы решали задачу для всех $i$ в интервале $0..n$).
В данном случае в задаче просят найти число последовательностей, в которых никакие две единицы не стоят рядом. Чтобы понять, что является состоянием, надо задать себе вопрос<center>"Что надо знать про задачи меньшего размера, чтобы найти ответ на текущий вопрос?"</center>
:::info
Динамика -- это умная замена рекурсивного перебора. Когда надо что-то перебрать, мы делаем шаги из одного состояния в другое. Чтобы определить динамику, надо ответить на следующие вопросы:
<br>
<div class="alert alert-warning">
Q: чем описываются состояния?<br>
A: чаще всего – какие-то из ограничений на ввод + дополнительная информация, которая определяется структурой задачи
</div>
<div class="alert alert-warning">
Q: какая дополнительная информация нужна?<br>
A: надо посмотреть на то, какие описания состояний гарантированно позволяют задать переходы между ними
</div>
<div class="alert alert-warning">
Q: что такое переход между состояниями?<br>
A: <ol>
<li>выбирается состояние, для которого решить задачу просто (обычно оно соответствует минимальным ограничениям ввода)</li>
<li>находится простое правило, по которому из ответов для "более простых" состояний можно получить ответ для "более сложных"</li>
<li>определяется порядок обхода, в котором "более сложные" состояния будут посещены позже "более простых"</li></ol>
</div>
:::
Попробуем посмотреть на те же вопросы в рамках данной задачи:
1. состояние описывается парой $(i, c_{last})$, где $i$ -- длина желаемой строки, а $c_{last}$ -- последний символ в ней.
2. дополнительная информация -- это $c_{last}$
- если последний символ строки длины $i$ равен '1', то удалением последнего символа получается строка длины $i-1$, у которой на конце стоит '0'
- если последний символ строки длины $i$ равен '0', то удалением последнего символа получается строка длины $i-1$, у которой на конце стоит '0' или '1'
3. переходы:
- самое "простое" состояние -- $i = 1$
- как уже описано выше, количество строк длины $i$ с последним символом $c_{last}$ равно количеству строк длины $i-1$ с последним символом '0', плюс, если $c_{last} = \text{'0'}$, количеству строк длины $i - 1$ с последним символом '1'
- перебор осуществляется от меньших $i$ к большим
:::success
Это "соответствие" между строками длины $i$ и $i-1$ стоит воспринимать как "способ однозначно получить из одного другое и наоборот".
В данном случае этот способ описывается как "приписать $c_{last}$ в конец" и, обратно, "стереть последний символ".
В задачах вида "найти число способов" именно это взаимооднозначное соответствие позволяет нам считать, что число способов равно сумме числа способов "меньших" состояний.<br>
Если брать в качестве примера эту задачу, для примера, число способов построить такую последовательность длины $3$ с '1' на конце равно:
- числу способов построить последовательность длины $2$ с '0' на конце, что равно:
- числу способов построить последовательность длины $1$ с '0' на конце + числу способов построить последовательность длины $1$ с '1' на конце
$$\sharp(3, \text{'1'})\begin{cases}\\
\text{'001'}\\
\text{'101'}\\
\\\end{cases} \leftarrow \sharp(2, \text{'0'})
\begin{cases}
\text{'00'} \leftarrow \sharp(1, \text{'0'}) \begin{cases}\text{'0'}\end{cases}\\
\text{'10'} \leftarrow \sharp(1, \text{'1'}) \begin{cases}\text{'1'}\end{cases}
\end{cases}$$
:::
> [color=Green] [name=Задача "$i, c_{last}$"] Найти число строк из '0' и '1' длины $i$, не содержащих две '1' подряд и заканчивающихся на $c_{last}$.
Собственно, $d_{i, c_{last}}$ -- решение этой задачи. Тогда самая простая задача, которую мы можем решить -- это $i = 1$, и $$d_{1, \text{'0'}} = 1, d_{1, \text{'1'}} = 1$$ потому что есть ровно одна последовательность длины $1$ с заранее фиксированным последним символом.
Пересчитываем $d_{i, c_{last}}$ следующим образом (как описано выше):
- $d_{i, \text{'0'}} = d_{i-1, \text{'0'}} + d_{i-1, \text{'1'}}$, потому что перед '0' может следовать как '0', так и '1'
- $d_{i, \text{'1'}} = d_{i-1, \text{'0'}}$, потому что перед '1' не может находиться еще одна '1'
Ответ на исходную задачу -- это $d_{n, \text{'0'}} + d_{n, \text{'1'}}$, то есть количество таких последовательностей длины $n$ с любым символом на конце.
Таким образом, можно написать следующий код:
```cpp
unsigned int n;
cin >> n;
vector<pair<unsigned int, unsigned int>> d(n + 1);
/*
pair объект из двух других объектов
.first дает доступ к первому (у нас это d_{i, '0'})
.second дает доступ ко второму (у нас это d_{i, '1'})
*/
d[1] = make_pair(1, 1);
for (unsigned int i = 2; i <= n; i++) {
d[i].first = d[i - 1].first + d[i - 1].second;
d[i].second = d[i - 1].first;
}
cout << d[n].first + d[n].second << '\n';
```
Более того <span style="color:red">(!)</span>, существует <span style="color:red">альтернативное решение</span>, которое основывается на том, что $d_{i, \text{'1'}} = d_{i-1, \text{'0'}}$, а значит $$d_{i, \text{'0'}} = d_{i-1, \text{'0'}} + d_{i-1, \text{'1'}} = d_{i-1, \text{'0'}} + d_{i-2, \text{'0'}}$$
Благодаря этому, мы можем избавиться от состояний $d_{i, \text{'1'}}$, оставив только состояния $r_i = d_{i, \text{'0'}}$. Смысл этого состояния -- "количество строк длины $i$ с '0' на конце". Тогда:
- $r_0 = r_1 = 1$
- $r_i = r_{i-1} + r_{i-2}$, физический смысл чего формулируется как <center>"если на конце строки стоит больше одного '0', то таких строк ровно $r_{i-1}$, иначе количество равно $r_{i-2}$, потому что на конце обязана быть пара '10', а двух '1' подряд не бывает, значит на конце '010', и удалением последних двух символов мы получаем $r_{i-2}$ вариантов"</center>
- ответом будет (по аналогичным причинам) $r_{n} + r_{n-1}$
Получаем более короткое решение:
```cpp
unsigned int n;
cin >> n;
vector<unsigned int> d(n + 1);
d[0] = d[1] = 1;
for (unsigned int i = 2; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
cout << d[n - 1] + d[n] << '\n';
```
:::success
Наиболее внимательные могли заметить, что это по сути определение _чисел Фибоначчи_, и что на самом деле ответ на эту задачу -- это просто $n+1$-е число Фибоначчи, которые мы уже ранее считали в первой задаче контеста.
:::
Sign in with Wallet
Connect another wallet