\Section{Динамика}{16 октября}{Шавкунов Михаил}
Рассмотрим задачу калькулятор.
Хотим получить число N из 1 за минимальное число шагов.
У нас есть три вида операций: умножить на 2, умножить на 3 и прибавить единицу.\\
Определим f[x] - минимальное число ходов, чтобы из 1 получить x.\\
\Subsection{Динамика назад}\\
Состояния последовательно пересчитывается исходя из уже посчитанных.
f[1] = 0 - база\\
\[
	f[x] = min
        \left.
    	\begin{cases}
			f[x - 1] \\
    	 		f[x/2], & \text{если x $\vdots$ 2} \\
    	 		f[x/3], & \text{если x $\vdots$ 3} \\
		\end{cases}
        \right\} + 1
\]
Выбираем минимум из уже посчитанных значений и прибавляем 1, т.к. сделали 1 ход. Таким образом, нашли оптимальный ответ, свели задачу в к меньшим подзадачам.\\
Перебираем x в порядке возрастания:
\begin{code}
	f[1] = 0
	for x = 2...N
    		f[x] = ...
\end{code}
Асимптотика - $\Theta(N)$. Ответ лежит в ячейке f[N].\\
\Subsection{Динамика вперед}\\
Обновляются все состояния, зависящие от текущего состояния.
Пусть $f[i] = \infty$ $\forall i.$\\
Положим f[1] = 0  \\
\begin{code}
void relax(int &a, int b){
    a = max(a, b)
}
for x = 1..N - 1
    f[x + 1] = relax(f[x + 1], f[x] + 1)
    if 2x <= N
        f[2x] = relax(f[2x], f[x] + 1)
    if 3x <= N
        f[3x] = relax(f[3x], f[x] + 1)
\end{code}
Корректность доказывается по индукции. От текущего состояния у нас могут зависеть до 3 других состояний, поэтому каждый раз мы их обновляем. Результат будет корректен, поскольку f[x] у нас посчитано корректно, для других состояний мы не ухудшаем ответ.\\
\Subsection{Ленивая динамика(рекурсия)}\\
Добавим еще одну операцию в задачу - прибавить 2 к числу.\\
Напишем долгий перебор и оптимизуем его.\\
Заполним глобальный массив F бесконечностями.\\
\begin{code}
int f(int x){
    if (x == 1) return 0
    int &res = F[x] // `Запоминаем ссылку на res, в дальнейшем все действия с res будут изменять и F[x]`
    if (res != + `$\infty$`) // `наше значение уже было раньше посчитано, нет смысла его считать заново`       
    	return res
    relax(res, f(x - 1))
    if (x % 2 == 0)
        relax(res, f(x/2))
    if (x % 3 == 0)
        relax(res, f(x/3))
    if (x >= 3)
        relax(res, f(x - 2))
    return res += 1
}
\end{code}
Время перебора без отсечений. Верхняя оценка: $4^N$ - Можем применить одну из 4 операций N раз. Нижняя оценка : n-ое число Фибоначчи(т.к. вызываемся от f(x - 1) и от f(x - 2)). 
$4^N \geqslant Time \geqslant FibN = \phi^N$\\
У ленивой динамики есть 2 преимущества: \\
\begin{itemize}
	\item Не фиксированный порядок перебора
    \item Посещение только достижимых состояний
\end{itemize}
Все эти задачи можно свести к нахождению кратчайшего пути из 1 состояния в N-ое в ацикличном ориентированном графе, в котором вершины - состояния, ребро между состояниями - переход из одного в другое.\\
\Subsection{Что нужно знать для динамики}\\
\begin{itemize}
    \item Состояние динамики: параметр(ы), однозначно задающие подзадачу.
    \item Переходы между состояниями: формула пересчёта.
    \item Начало, т.е. значения начальных состояний.
    \item Порядок пересчёта.
    \item Положение ответа на задачу.
\end{itemize}
\Subsection{Граф состояний}\\
Мы можем сформулировать термины ленивой, вперед, назад динамики через ацикличный граф. Каждый раз когда мы делали переход - можно сказать, что мы переходили из одной вершины графа(вершина - состояние) в другую.
\begin{itemize}
    \item Ленивая динамика: происходит поиск в глубину из последней вершины к первой
    \item Динамика вперед: из каждой вершины мы релаксируем путь в другие в вершины.
    \item Динамика назад: Из всех путей ведущих в текущую вершину выбираем оптимальный.
\end{itemize}
\Subsection{Задача про путь в матрице}\\
Пусть дана матрица a[n, m]. Хотим найти путь минимальной стоимости, максимальной стоимости, количество путей из точки [1,1] в точку [n, m].\\
\begin{itemize}
    \item Состояние - [i, j], изначально все заполнено плюс или минус бесконечностями, в зависимости, что мы считаем: минимумальный или максимальный путь соотвественно.
    \item Переходы из [i, j] в [i + 1, j] и в [i, j + 1]
    \item Начало в [1, 1]
    \item Конец [n, m]
    \item Порядок: по порядку обрабатываем строчки сверху вниз.
\end{itemize}
Если мы считаем путь минимальной/максимальной стоимости то:\\
\begin{code}
	dp[i + 1, j] = min/max(dp[i, j] + a[i, j], dp[i + 1, j];
	dp[i, j + 1] = min/max(dp[i, j] + a[i, j], dp[i, j + 1];
\end{code}
Если мы считаем количество путей, то тогда количество в следующую ячейку будет равнятся сумме двух ячеек, из которых можно прийти. Изначально dp[1, 1] = 1. В dp[n, m] будет лежать ответ.