\Section{Динамическое программирование}{19 октября}{Веселов Иван}
	\Subsection{Редакционное расстояние (расстояние Левенштейна)}\\
    \Subsubsection{Постановка задачи}\\
      Даны строки $s$ и $t$. Разрешается изменять строку $s$ с помощью трех операций:
      \begin{itemize}
        \item[1.] Вставить новый символ в любое место в строке.
        \item[2.] Удалить любой символ из строки.
        \item[3.] Изменить любой символ строки.
      \end{itemize}
      Требуется за наименьшее число операций получить из строки $s$ строку $t$.
      
    \Subsubsection{Решение}\\
      \begin{Def}
        Преобразованием будем называть некоторую последовательность операций над строкой $s$, в результате выполнения которых получается
        строка $t$.
      \end{Def}
      
      \begin{Thm}
        В любом преобразовании, число операций в котором наименьшее возможное, над каждым символом строки $s$ производится не более
        одной операции, а над каждым добавленным символом операции не производятся.
      \end{Thm}
        \begin{proof}
          Зафиксируем некоторое преобразование с наименьшим числом операций $P$, любой символ строки $s$ и посмотрим на то, что с этим
          символом происходило в преобразовании $P$. Обозначим этот символ --- $c$. После выполнения всех операций $c$ был либо удален,
          либо стал некоторым символом из строки $t$, причем возможно над $c$ была применена операция изменения. Если $c$ был удален и
          над ним применялись некоторые операции изменения, то их можно убрать из $P$ и получить преобразование с меньшим числом операций.
          Если $c$ не удалялся и изменялся несколько раз, то можно убрать из $P$ все операции изменения $c$, кроме последней, и получить
          преобразование с меньшим числом операций.\\
          Теперь зафиксируем любой добавленный операцией символ $d$ (если такой существует). Если после выполнения всех операций $d$ удален,
          то можно убрать из $P$ все операции связанные с $d$ и получить преобразование с меньшим числом операций. Если в $P$ есть операции
          изменяющие $d$, то можно все эти операции убрать из $P$, а добавить $d$ со знчением, на которое изменяла $d$ последняя операция
          изменения. Тогда получится преобразование с меньшим числом операций.
        \end{proof}
      
      \begin{Rem}
        В любом преобразовании с наименьшим числом операций неважно в каком порядке выполнять операции.
        \begin{proof}
          Каждая операция выполняется над символом. Если поменять местами две операции над различными символами, то ничего не изменится.
          В преобразовании с наименьшим числом операций над каждый символом выполняется не больше одной операции, значит можно менять
          местами любые две операции, так как они производятся над разными символами.
        \end{proof}
      \end{Rem}
      
      \begin{Def}
        $f_{i, j}$ --- редакционное расстояние между префиксом строки $s$ длинны $i$ и префиксом строки $t$ длинны $j$.
      \end{Def}
      
      Для того, чтобы ввести соотношение для $f_{i, j}$, нужно перебрать, какой символ после выполнения операций будет соответствовать
      символу $t_j$:
      \begin{itemize}
        \item[1.] Добавленный символ. Тогда $f_{i, j} = f_{i, j - 1} + 1$, то есть наименьшее число операций, чтобы преобразовать префикс $s$
        длины $i$ в префикс $t$ длины $j-1$ и еще одна операция добавления символа $t_j$.
        \item[2.] $s_i$. Тогда если $s_i = t_j$, то $f_{i, j} = f_{i - 1, j - 1}$, иначе $f_{i, j} = f_{i - 1, j - 1} + 1$. То есть наименьшее
        число операций для оставшихся символом и возможно еще операция изменения символа $s_i$ в $t_j$, если они различаются.
        \item[3.] Символ из $s$, но не $s_i$. Тогда символ $s_i$ не может быть не удален, так как тогда не понятно, какому символу из $t$
        он будет соответствовать. Значит $f_{i,j} = f_{i - 1, j} + 1$, то есть наименьшее число операций для оставшихся символов и еще
        одна операция удаления.
      \end{itemize}
      
      Среди всех вариантов для $f_{i,j}$ нужно выбрать минимум.\\
      
      \begin{itemize}
      \item Так как $f_{i, j}$ зависит от значений $f$ с меньшими индексами, то для вычисления
      $f$\ $i$ и $j$ нужно перебирать в порядке увеличения.
      \item Для восстановления ответа можно ходить по обратным ребрам в графе.
      \item Заметим, что к данному решению можно применить метод Хиршберга
      \end{itemize}
    
	\Subsection{Наибольший общий префикс (Longest Common Prefix, LCP)}\\
    \Subsubsection{Постановка задачи}\\
      Даны строки $s$ и $t$. Требуется посчитать $f_{i,j}$ --- наибольший общий префикс суффикса $s$ длины $i$ и суффикса $t$ длины $j$.
      
    \Subsubsection{Решение}\\
      Если $s_i \neq t_j$, то $f_{i, j} = 0$, иначе, если строки не кончились, то $f_{i, j} = f_{i + 1, j + 1} + 1$. То есть либо у строк нет
      общих префиксов, либо первые символы совпадают и каждый общий префикс является общим префиксом строк без первого символа.\\
      Так как $f_{i, j}$ зависит от значений $f$ с большими индексами, то для вычисления $f$\ $i$ и $j$ нужно перебирать в порядке уменьшения.
      
  \Subsection{Наибольшая подпоследовательность палиндром}\\
    \Subsubsection{Постановка задачи}\\
      Дана строка $s$. Требуется найти самую длинную подпоследовательность $s$, которая является плиндромом.
      
    \Subsubsection{Решение}\\
      \begin{Def}
        $f_{l, r}$ --- ответ на задачу для подстроки строки $s$, начинающейся с символа, стоящего на $l$-ой позиции, и заканчивающейся
        символом, стоящим на $r$-ой позиции.
      \end{Def}
      
      Для того, чтобы ввести соотношение для $f_{l, r}$, нужно перебрать, есть ли в ответе символы на $l$-ой и $r$-ой позициях:
      \begin{itemize}
        \item[1.] Символ на $l$-ой позиции не входит в ответ. Тогда $f_{l, r} = f_{l + 1, r}$.
        \item[2.] Символ на $r$-ой позиции не входит в ответ. Тогда $f_{l, r} = f_{l, r - 1}$.
        \item[3.] Символы на $l$-ой и $r$-ой позициях входят в ответ. Но тогда они должны быть равны, так как один из них первый символ
        в ответе, а другой последний. Если они равны, то $f_{l, r} = f_{l + 1, r - 1} + 1$.
      \end{itemize}
      
      Среди всех вариантов для $f_{l, r}$ нужно выбрать максимальный.\\
      
      \begin{itemize}
      \item Так как $f_{l, r}$ зависит от значений $f$, у которых $r - l$ меньше, то сначала нужно перебирать $r - l$, а затем один из индексов
      в любом порядке.
      \item Для восстановления ответа можно ходить по обратным ребрам в графе.
      \end{itemize}
      
  \Subsection{Наибольшая возрастающая подпоследовательность (Longest Increasing Subsequence, LIS)}\\
    \Subsubsection{Постановка задачи}\\
      Дана последовательность $a_n$. Требуется найти у нее наибольшую строго возрастающую подпоследовательность.
      
    \Subsubsection{Решение \#1}\\
      \begin{Def}
        $f_i$ --- наибольшая возрастающая подпоследовательность $a_n$, оканчивающаяся $i$-ым элементом.
      \end{Def}
      
      Для того, чтобы ввести соотношение для $f_i$, нужно перебрать предыдущий элемент подпоследовательности. Получится, что
      $f_i = \min\limits_{j < i,\ a_j < a_i}{\{f_j\}} + 1$.\\
      \begin{itemize}
        \item Так как $f_i$ зависит только от значений $f$ с меньшими индексами, то для вычисления $f$ нужно перебирать $i$
        в порядке возрастания.
        \item Ответом для всей задачи является $\max{\{f_i\}}$.
        \item Для восстановления ответа можно ходить по обратным ребрам в графе. 
      \end{itemize}
      
    \Subsubsection{Решение \#2}\\
      \begin{Def}
        $g_{i, j}$ --- наименьший элемент (по значению) на который может оканчиваться возрастающая подпоследовательность длины $j$,
        состоящая из элементов префикса последовательности $a_n$ длины $i$, либо $+\infty$, если подпоследовательностей с такими
        свойствами не существует.
      \end{Def}
      
      Возможно два случая:
      \begin{itemize}
        \item[1.] Элемент $a_i$ не принадлежит подпоследовательности. Тогда $g_{i, j} = g_{i - 1, j}$.
        \item[2.] Элемент $a_i$ принадлежит подпоследовательности. Тогда если его убрать из подпоследовательности, то
        получится возрастающая подпоследовательность длины $j - 1$ из первых $i - 1$ элементов $a_n$, у которой последний элемент
        будет меньше, чем $a_i$. Наоборот, если существует возрастающая подпоследовательность первых $i - 1$ элементов $a_n$ длины
        $j - 1$ такая, что ее последний элемент меньше $a_i$, то к ней можно добавить в конец $a_i$ и получить возрастающую
        подпоследовательность длины $j$. Теперь, если $g_{i - 1, j - 1} < a_i$, то существует возрастающая подпоследовательность
        первых $i$ элементов $a_n$ длины $j$, оканчивающаяся $a_i$, в таком случае $g_{i, j} = a_i$. Если $g_{i - 1, j - 1} \geq a_i$,
        то искомой последовательности для $g_{i, j}$ не существует, так как в противном случае можно было бы убрать из этой
        подпоследовательности последний элемент $a_i$ и получить возрастающую подпоследовательность длины $j - 1$, у которой
        последний элемент меньше, чем $g_{i - 1, j - 1}$. Но это противоречит определению $g_{i - 1, j - 1}$.
      \end{itemize}
      
      Среди всех вариантов для $g_{i, j}$ нужно выбрать минимальный.\\
      \begin{itemize}
        \item Так как $g_{i, j}$ зависит только от значений $g$ с меньшими индексами, то для вычисления $g$ нужно перебирать $i$ и $j$
        в порядке возрастания.
        \item Ответом для всей задачи является $\max\limits_{j|g_{n, j} \neq +\infty}{\{j\}}$.
        \item Для восстановления ответа можно ходить по обратным ребрам в графе. 
      \end{itemize}
      
    \Subsubsection{Решение \#3}\\
      Начнем оптимизировать второе решение.
      \begin{Lm}
        При фиксированном $i$: $g_{i, j} \leq g_{i, j + 1}$, то есть $g_i$ не убывает.
          \begin{proof}
            Пусть $\exists j: g_{i, j} > g_{i, j + 1}$, тогда $g_{i, j} \neq +\infty$, так как существует возрастающая
            подпоследовательность длины $j + 1$, поскольку $g_{i, j + 1} < g_{i, j} \leq +\infty$, и из нее можно убрать последний элемент и
            получить некоторую возрастающую подпоследовательность длины $j$.\\
            Но тогда существуют соответствующие возрастающие подпоследовательноти $a_{k}^{j+1}$ длины $j+1$ и $a_{l}^{j}$ длины $j$.
            Но если последний элемент $a_{k}^{j+1}$ меньше, чем последний элемент $a_{l}^{j}$, то предыдущий элемент
            $a_{k-1}^{j+1} < a_{k}^{j+1} < a_{l}^{j}$ тоже меньше последнего элемента $a_{l}^{j}$. Но тогда,
            последовательность $a^{j+1}$ без последнего элемента является возрастающей подпоследовательностью длины $j$, и ее последний
            элемент меньше, чем $g_{i, j}$, но это противоречит определению $g_{i, j}$.
          \end{proof}
      \end{Lm}
      
      \begin{Lm}
        Для фиксированного $i$\ $g_{i}$ отличается от $g_{i - 1}$ не более, чем в одном элементе,
        $g_{i,j_1} \neq g_{i-1, j_1}, g_{i,j_2} \neq g_{i-1, j_2} \Rightarrow j_1 = j_2$. Т.е. при пересчете $g_{i}$ через $g_{i-1}$
        значение улучшится только в одном элементе.
        \begin{proof}
          Т.к. последовательность $g_{i - 1}$ не убывает, то ее можно поделить на три последовательные части:
          элементы меньшие $a_i$, элемент-$lower_bound$\ $a_i$, все остальные элементы. Пусть $lower\_bound$\ $a_i$ --- $g_{i - 1, b}$.
          Все элементы меньшие $a_i$ не могут быть улучшены, т.к. для каждого из них существует возрастающая подпоследовательность,
          оканчивающаяся на элемент меньший $a_i$. Значение $g_{i, b} = a_i$, по правилу пересчета, так как $g_{i-1, b-1} < a_{i}$ или,
          в случае, когда $b=1$, не существует. Аналогично по правилу пересчета все остальные элементы не изменяются, так как
          $\forall j > b: g_{i-1, j-1} \geq a_i$.
        \end{proof}
      \end{Lm}
      
      Теперь, вместо линейного пересчета, при переходе от $g_{i-1}$ к $g_{i}$, будем пользоваться бинарным поиском по $g_{i-1}$, чтобы
      найти элемент, который может измениться. Остается лишь считать $g$ не в двухмерном массиве, а хранить только $g_i$ и получать
      из него $g_{i+1}$, изменяя не более одного элемента.\\
      Для восстановления ответа нужно поддерживать последовательность $p_i$, которая формируется следующим образом: когда пересчитывается
      $g_{i}$ --- $g_{i - 1, b}$ это $lower\_bound$\ $a_i$, тогда $p_i$ равняется индексу элемента, который записан в $g_{i-1, b-1}$, или ничему,
      если $b = 1$. Таким образом поддерживается инвариант, что, если элемент $a_k$ был записан в $g_{i, j}$, то $p_k$ указывает на
      меньший индекс меньшего элемента, причем, пройдя по этим «ссылкам», можно получить возрастающую подпоследовательность длины $j$ в обратном порядке.
      
  \Subsection{Скобочная последовательность (Динамика по подотрезкам)}\\
    \Subsubsection{Постановка задачи}\\
      Дана скобочная последовательность $s$ из разных типов скобок. Нужно удалить минимальное количество скобок так, чтобы оставшаяся
      последовательность стала правильной скобочной последовательностью.
      
    \Subsubsection{Решение}\\
      \begin{Def}
        $f_{l, r}$ --- минимальное количество скобок, которое нужно удалить из подстроки $s$, начинающейся в позиции $l$ и
        заканчивающейся в позиции $r$, чтобы получить из этой подстроки правильную скобочную последовательность.
      \end{Def}
      
      Для того, чтобы ввести соотношение для $f_{l, r}$, нужно перебрать, что произойдет со скобкой в позиции $l$:
      \begin{itemize}
        \item[1.] Скобка будет удалена. Тогда $f_{l, r} = f_{l + 1, r} + 1$, или $f_{l, r} = 1$, если $l = r$.
        \item[2.] Скобка не будет удалена, тогда найдется парная ей скобка. Пусть эта парная скобка находится на позиции $m$, тогда
        из $s_{l + 1, m - 1}$ нужно удалить некоторые скобки, чтобы получить правильную скобочную последовательность и аналогично с
        $s_{m + 1, r - 1}$. То есть нужно перебрать парную скобку для скобки на позиции $l$ и по всем вариантам взять минимум:
        $f_{l, r} = \min\limits_{m}{f_{l + 1, m - 1}, f_{m + 1, r - 1}}$.
      \end{itemize}
      
      Среди всех вариантов для $f_{l, r}$ нужно выбрать минимальный.\\
      
      \begin{itemize}
      \item Так как $f_{l, r}$ зависит от значений $f$, у которых $r - l$ меньше, то сначала нужно перебирать $r - l$, а затем один из индексов
      в любом порядке.
      \item Для восстановления ответа можно ходить по обратным ребрам в графе.
      \end{itemize}