dynamic-programming.tex

\chapter{Динамично програмиране}

\section{Какво е динамично програмиране?}

Динамичното програмиране не е нито динамично, нито програмиране.
Това е както оптимизационен метод, така и алгоритмична парадигма, която е разработена от Ричард Белман през 50-те години на миналия век.
В този метод една зачача се разделя на подзадачи по рекурсивен начин.
Той се използва в два случая:
\begin{itemize}
    \item при задачи, които имат припокриваща се подструктура т.е. задачата се разделя на подзадачи, които се срещат няколко пъти;
    \item при задачи, които имат оптимална подструктура т.е. оптимално решение може да се конструира от оптимални решения на подзадачите.
\end{itemize}

\section{Прости примери за динамично програмиране}

Да кажем, че искаме да сметнем $n$-тото число на Фибоначи.
Един начин е да караме по рекурентното уравнение:
\lstinputlisting{algorithms/fib-slow.txt}
Проблемът е, че получаваме експоненциална сложност по време.
Нещо, което можем да направим, е да пазим вече пресметнатите стойности, за да не се налага да ги пресмятаме пак:
\lstinputlisting{algorithms/fib-dp.txt}
Това е пример за задача с припокриваща се подструктура, с решение по схемата \textbf{динамично програмиране}.
Успяхме да решим задачата за линейно време.

Нека сега видим пример за задача с оптимална подструктура.
Да кажем, че имаме два низа $S_1[1 \dots n]$ и $S_2[1 \dots m]$ и искаме да пресметнем дължината на най-дългата обща подредица на $S_1$ и $S_2$.
Лесно се вижда, че дължината $\operatorname{LCS}_{S_1, S_2}(i, j)$ на най-дългата подредица на $S_1[1 \dots i]$ и $S_2[1 \dots j]$ може да се пресметне рекурсивно така:
\[
    \operatorname{LCS}_{S_1, S_2}(i, j) = \begin{cases}
        0                                                                                          & \text{, ако } i = 0 \text{ или } j = 0               \\
        \operatorname{LCS}_{S_1, S_2}(i - 1, j - 1) + 1                                            & \text{, ако } i, j > 0 \text{ и } S_1[i] = S_2[j]    \\
        \max\{ \operatorname{LCS}_{S_1, S_2}(i - 1, j), \operatorname{LCS}_{S_1, S_2}(i, j - 1) \} & \text{, ако } i, j > 0 \text{ и } S_1[i] \neq S_2[j]
    \end{cases}
\]
Ако искаме да пресметнем това със обикновена рекурсия, отново ще получим експоненциална сложност по време.
Отново можем да направим решение по схемата \textbf{динамично програмиране} със сложност $\Theta(n \cdot m)$.
Единственото, което трябва да се направи, е да се измисли последователност за пресмятане на:
\[
    \begin{pmatrix}
        \operatorname{LCS}_{S_1, S_2}(0, 0) & \dots  & \operatorname{LCS}_{S_1, S_2}(n, 0) \\
        \vdots                              & \ddots & \vdots                              \\
        \operatorname{LCS}_{S_1, S_2}(m, 0) & \dots  & \operatorname{LCS}_{S_1, S_2}(n, m)
    \end{pmatrix}
\]
Важно е да искаме преди пресмятането на всяка клетка, необходимите за нея данни вече са готови.
Ето как може да стане това:
\lstinputlisting{algorithms/longest-common-subsequence.txt}

\section{Динамично програмиране за решаване на комбинаторни задачи}

Вижда се, че тази техника е много удобна за бързо пресмятане на рекурентни зависимости.
Едно приложение е в решаването на комбинаторни задачи.
Да кажем, че искаме да пресметнем бързо ${n \choose k}$.

Нека първо си припомним дефиницията:
\[
    {n \choose k} = \frac{n!}{k! (n - k)!}.
\]

Ние ще пресметнем ${n \choose k}$ точно по този начин.
За тази цел единственото нещо, което се иска да сметнем трите стойности -- $n!, k!$ и $(n - k)!$.

\newpage

Това става елементарно по следния начин:
\lstinputlisting{algorithms/binomial-factorial.txt}
Получихме сложност по време $\Theta(n)$ т.е. имаме сравнително бързо решение.
Обаче то не е практично.
Проблемът е, че функцията $n!$ расте много бързо.
Ние ще работим с големи стойности във $F[0 \dots n]$, но крайният отговор ще е много по-малък от това.
Ако искаме да си гарантираме възможно най-малки стойности по време на изчисление, трябва да го пресметнем за време $\Theta(n \cdot k)$ чрез формулата:
\[
    {n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k}.
\]

Нека сега се опитаме да пресметнем броят $T_n$\footnote{Тези числа се наричат числа на Каталан.} на двоични дървета за търсене с $n$ различни върха.
При $n = 0$ положението е ясно.
Ако $n \geq 1$, то имаме няколко случая в зависимост от това кой връх е корен на дървото.
Броят на двоичните дървета за търсене с корен $i$-тия по големина връх, където $1 \leq i \leq n$, е равен на броя двоичните дървета с $(i - 1)$-те по-малки от него върха, умножен по броя на двоичните дървета с останалите $n - i$ върха.
Това е точно $T_{i - 1} \cdot T_{n - i}$.
Така получаваме следното рекурентно уравнение:
\begin{align*}
    T_0 & = 1                                                                 \\
    T_n & = \sum\limits_{i = 1}^n T_{i - 1} \cdot T_{n - i} \text{ за } n > 0
\end{align*}
Ясно е, че не искаме да пресмятаме $T_n$ чрез рекурсия -- това би било кошмарно бавно.

\newpage

Отново ще помним предишни изчисления, за да си забързаме алгоритъма до такъв със сложност $\Theta(n^2)$:
\lstinputlisting{algorithms/catalan.txt}

\section{Два интересни примера}

За първия пример, нека имаме някакъв краен речник $D$ от непразни думи над $\Sigma = \{ a, \dots, z \}$.
Ще искаме при подаден низ над $\Sigma$ да видим дали той може да се разбие на думи от речника (с възможни повторения).
Нека например да вземем речника $D = \{ \text{mango}, \text{i}, \text{icecream}, \text{like}, \text{with} \}$.
Тогава думата ``ilikeicecreamwithmango'' може да се разбие на ``i like icecream with mango''.

Нека е подаден един низ $\alpha \in \Sigma^*$.
Ако $\alpha = \varepsilon$, то тогава очевидно можем да получим $\alpha$ чрез конкатенация на думи от $D$.
Ако $\alpha \neq \varepsilon$ и $\alpha$ се получава чрез конкатенация на думи от $D$, то тогава има $\beta \in \Sigma^*$ и $\gamma \in D$, за които е изпълнено, че $\alpha = \beta \gamma$ и $\beta$ може да се получи чрез думи от $D$.
Но $\gamma \neq \varepsilon$, т.е. успяхме да сведем задачата за $\alpha$ до задача за $\beta$, като $|\beta| < |\alpha|$.
Нека сега да формализираме тези разсъждения.
Нека $\alpha = \alpha_1 \dots \alpha_n$, където $\alpha_i \in \Sigma$.
Тогава булевата функция $\operatorname{WB}_{D, \alpha}(i)$, която казва дали $\alpha_1 \dots \alpha_i$ може да се разбие на думи от $D$, изглежда така:
\[
    \operatorname{WB}_{D, \alpha}(i) = \begin{cases}
        \T                                                                                                                                 & \text{, ако } i = 0 \\
        \bigvee\limits_{\beta \in D} (\alpha_{i - |\beta| + 1} \dots \alpha_i = \beta \: \& \: \operatorname{WB}_{D, \alpha}(i - |\beta|)) & \text{, иначе}
    \end{cases}
\]

\newpage

На нас това, което ни трябва, е $\operatorname{WB}_{D, \alpha}(|\alpha|)$.
С малко мислене върху това как се пресмята $\operatorname{WB}_{D, \alpha}$, човек може да стигне до следното итеративно решение:
\lstinputlisting{algorithms/word-break.txt}
Да направим сега малко анализ.
Ако $|\alpha| = n, |D| = m$, и $\max \{ |\beta| \mid \beta \in D \} = k$, то това решение има сложност по време $O(n \cdot m \cdot k)$, понеже за всяко $1 \leq i \leq n$ и за всяка дума $\beta \in D$ (те са $m$ на брой) проверяваме дали $\alpha_{i - |\beta| + 1} \dots \alpha_i = \beta$, което става за време $O(k)$, и дали $\operatorname{WB}_{D, \alpha}(i - |\beta|) = \T$, което поради наличието на масива $WB[0 \dots n]$ става за константно време.

Този масив доста помага, ако не го бяхме ползвали, сложността щеше да се опише (горе долу) с рекурентното уравнение:
\begin{align*}
    T(n) = \sum\limits_{i = 1}^{n} (m \cdot k \cdot T(n - i)) + \Theta(1) & = m \cdot k \cdot \sum\limits_{i = 0}^{n - 1} T(i) + \Theta(1)                            \\
                                                                          & = m \cdot k \cdot T(n - 1) + m \cdot k \cdot \sum\limits_{i = 0}^{n - 2} T(i) + \Theta(1) \\
                                                                          & = m \cdot k \cdot T(n - 1) + T(n - 1)                                                     \\
                                                                          & = (m \cdot k + 1) T(n - 1).
\end{align*}

В този случай $T(n) \asymp (m \cdot k + 1)^n$.

В горния алгоритъм сложността по памет очевидно е $\Theta(n)$, заради допълнителния масив, който заделяме.

Вторият пример ще бъде под формата на игра.
Наредени са $n$ монети със стойности съответно $v_1, \dots, v_n$.
Редуваме се с опонент да теглим една монета от избран от краищата на редицата, докато монетите не свършат.
Накрая всеки човек печели толкова, колкото е изтеглил.
В случай че играем първи, каква печалба можем да си гарантираме?

Първо да започнем с двата най-прости типа игри -- с една или две монети.
В играта с една монета е ясно, че най-голямата печалба, която можем да си гарантираме, е стойността на монетата.
В игра с две монети със стойности съответно $v_1, v_2$, най-голямата гарантирана печалба е очевидно $\max \{ v_1, v_2 \}$.

Нека сега в общия случай имаме следната партия:
\begin{center}
    \dc{$v_1$} \dc{$v_2$} \dt{$\dots$} \dc{$v_{n - 1}$} \dc{$v_n$}
\end{center}
Ще се опитаме да сведем тази по-сложна партия, до няколко по-прости.
Имаме две възможности:
\begin{enumerate}
    \item Ако изберем първата монета, опонента ще трябва да избира в конфигурацията:
          \begin{center}
              \dc{$v_2$} \dc{$v_3$} \dt{$\dots$} \dc{$v_{n - 1}$} \dc{$v_n$}
          \end{center}
          Той също има две възможности:
          \begin{enumerate}
              \item Ако опонента избере първата монета, ни оставя в конфигурацията:
                    \begin{center}
                        \dc{$v_3$} \dc{$v_4$} \dt{$\dots$} \dc{$v_{n - 1}$} \dc{$v_n$}
                    \end{center}
                    Тук можем да си мислим, че ние сме си заделили на страна печалба $v_1$, опонента си е заделил на страна печалба $v_2$, и играта започва наново в горната конфигурация.
              \item Ако пък избере последната монета, ни оставя в конфигурацията:
                    \begin{center}
                        \dc{$v_2$} \dc{$v_3$} \dt{$\dots$} \dc{$v_{n - 2}$} \dc{$v_{n - 1}$}
                    \end{center}
                    Тук можем да си мислим, че ние сме си заделили на страна печалба $v_1$, опонента си е заделил на страна печалба $v_n$, и играта започва наново в горната конфигурация.
          \end{enumerate}
    \item Ако изберем последната монета, опонента ще трябва да избира в конфигурацията:
          \begin{center}
              \dc{$v_1$} \dc{$v_2$} \dt{$\dots$} \dc{$v_{n - 2}$} \dc{$v_{n - 1}$}
          \end{center}
          Той също има две възможности:
          \begin{enumerate}
              \item Ако опонента избере първата монета, ни оставя в конфигурацията:
                    \begin{center}
                        \dc{$v_2$} \dc{$v_3$} \dt{$\dots$} \dc{$v_{n - 2}$} \dc{$v_{n - 1}$}
                    \end{center}
                    Тук можем да си мислим, че ние сме си заделили на страна печалба $v_n$, опонента си е заделил на страна печалба $v_1$, и играта започва наново в горната конфигурация.
              \item Ако пък избере последната монета, ни оставя в конфигурацията:
                    \begin{center}
                        \dc{$v_1$} \dc{$v_2$} \dt{$\dots$} \dc{$v_{n - 3}$} \dc{$v_{n - 2}$}
                    \end{center}
                    Тук можем да си мислим, че ние сме си заделили на страна печалба $v_n$, опонента си е заделил на страна печалба $v_{n - 1}$, и играта започва наново в горната конфигурация.
          \end{enumerate}
\end{enumerate}

Нека $\operatorname{MP}(i, j)$ е максималната печалба, която може да се спечели от първия играч (в първоначалната игра), ако може да събира монети със стойности съответно $v_i, \dots, v_j$.
По предните разсъждения можем да пресметнем тази печалба рекурсивно така:
\[
    \operatorname{MP}(i, j) = \begin{cases}
        v_i                                                                                         & \text{, ако } i = j     \\
        \max \{ v_i, v_j\}                                                                          & \text{, ако } i = j + 1 \\
        \!\begin{aligned}
              \max \{ & v_i + \min \{ \operatorname{MP}(i + 2, j), \operatorname{MP}(i + 1, j - 1) \}, \\
                      & v_j + \min \{ \operatorname{MP}(i, j - 2), \operatorname{MP}(i + 1, j - 1) \}
              \}
          \end{aligned} & \text{, иначе}
    \end{cases}
\]
Във хода на втория играч минимизираме, защото той печели възможно най-много, когато ние печелим възможно най-малко.
За задача на читателя оставяме да пресметне $\operatorname{MP}(1, n)$ итеративно.

\section{Задачи}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който пресмята ${n \choose k}$ с рекурентната формула от по-горе.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подадено естествено число $n$, намира броят на начини човек да се изкачи по тях, като може да изкачва най-много $3$ стъпала наведнъж.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подадена булева матрица $A[1 \dots n, 1 \dots m]$ намира броя на пътищата (движейки се само надясно и надолу) от $(1, 1)$ до $(n, m)$, които не минават през $1$ в $A$.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подадена матрица от естествени числа $A[1 \dots n, 1 \dots m]$ намира минималната цена на път (движейки се само надясно и надолу) от $(1, 1)$ до $(n, m)$, като под цена на път разбираме сумата на всичките $A[i, j]$, срещнати по пътя.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}


\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подаден целочислен масив $A[1 \dots n]$ намира дължината на най-дългата строго растяща негова подредица.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подаден масив от естествени числа $A[1 \dots n]$ и естествено число $s$ намира броя на начините, по които могат да се изберат елементи на $A$, така че да сумата им да е $s$.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
За масив от положителни числа $A[1 \dots n]$ и $1 \leq i < j \leq n$ казваме, че можем да стигнем от $i$ до $j$ в $A$ за една стъпка, ако и $j - i \leq A[i]$.
Да се напише колкото се може по-бърз алгоритъм, който при подаден масив от положителни числа $A[1 \dots n]$ намира минималния брой стъпки, с който можем да стигнем от $1$ до $n$ в $A$.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подадено $n$ и число $k$ пресмята броят на начините да се стигне до $k$ чрез хвърляния на зар с $n$ страни, на които пише числата от $1$ до $n$.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Формула ще наричаме всеки низ от вида $B_0 \sigma_1 B_1 \sigma_2 B_2 \dots B_{n - 1} \sigma_n B_n$, където $B_i \in \{ \T, \F \}$ и $\sigma_i \in \{ \lor, \land, \oplus \}$.
Например низът $\T \land \T \oplus \F \lor \T$ е формула.
В зависимост от това как слагаме скобите, оценката на израза може да е различна.
Например изразът $(\T \land (\T \oplus (\F \lor \T)))$ се остойностява като $\F$, докато изразът $(\T \land ((\T \oplus \F) \lor \T)))$ се остойностява като $\T$, въпреки че и двата израза се получават от примерната формула.
Да се напише колкото се може по-бърз алгоритъм, който при подадена формула да върне броят на различни скобувания, за които съответния израз се остойностява като $\T$.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Имаме професионален крадец, който иска да ограби къщите в дадена улица.
Проблемът е, че ако той ограби две съседни къщи, алармата ще се активира и полицията ще дойде.
Той не иска това, защото в такъв случай няма да спечели нищо.
Да се напише колкото се може по-бърз алгоритъм, който при подаден масив от естествени числа $L[1 \dots n]$, където $L[i]$ е печалбата от къща $i$, връща максималната печалба на крадеца.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Да се напише колкото се може по-бърз алгоритъм, който при подадена булева матрица $M[1 \dots n, 1 \dots m]$ намира най-голямото квадратче в $M$, съставено от $1$, и връща неговото лице.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Нека $n, l, r \in \N$ и $l \leq r$.
Един целочислен масив $A[1 \dots n]$ ще наричаме $(n, l, r)$-интересен, ако:
\begin{itemize}
    \item $l \leq A[i] \leq r$ за всяко $1 \leq i \leq n$;
    \item $\sum\limits_{i = 1}^n A[i] \equiv 0 \; (\operatorname{mod} 3)$.
\end{itemize}
Да се напише колкото се може по-бърз алгоритъм, който при подадени $n, l, r \in \N$, за които $l \leq r$, връща броя на $(n, l, r)$-интересни масиви.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Един целочислен масив $A[1 \dots n]$ наричаме аритметичен, ако за всяко $1 \leq i \leq n - 2$ е изпълнено, че $A[i + 2] - A[i + 1] = A[i + 1] - A[i]$.
Да се напише колкото се може по-бърз алгоритъм, който при подаден целочислен масив $A[1 \dots n]$ намира броя на подредиците на $A$, които са аритметични масиви.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Имаме $n$ на брой къщи, които искаме да боядисаме със цветове $c_1, c_2, c_3$, като не може две съседни къщи да имат еднакъв цвят.
Масив на цените ще наричаме всеки двумерен масив от положителни числа $P[1 \dots n, 1 \dots 3]$, където $P[i, j]$ ще бъде цената за боядисване на къща $i$ със цвят $c_j$.
Да се напише колкото се може по-бърз алгоритъм, който при подаден двумерен масив от положителни числа, намира минималната цена за боядисване на всички къщи.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}

\begin{problem}
Върху един масив от естествени числа $A[1 \dots n]$ можем да прилагаме следните две операции:
\begin{itemize}
    \item да увеличим $A[i]$ с единица за някое $1 \leq i \leq n$;
    \item да намалим $A[i]$ с единица за някое $1 \leq i \leq n$.
\end{itemize}
Да се напише колкото се може по-бърз алгоритъм, който при подаден масив от естествени числа $A[1 \dots n]$ връща минималния брой операции, които са нужни, за да стане масива монотонно ненамаляващ.
След това да се докаже неговата коректност, и да се изследва сложността му по време.
\end{problem}