Динамично по профил

Това понятие обикновено се използва при динамични за някакъв тип броене в таблица $n$x$m$, където едното измерение е малко, а другото е огромно (например от порядъка на $10^9$ или даже $10^{18}$. Нека за улеснение на обяснението и конкретика, приемем, че броят редове $n$ е малък, а броят колони $m$ е голям. Тогава трябва по подходящ начин да намерим подробно и еднотипно описание на колоната, което ще наричаме профил на колоната (по принцип то не трябва да зависи от конкретния номер на колоната). Понеже броят редове е малък в една колона, то различните профили на колоната трябва да са достатъчно малко, за да приложим техниката динамично по профил. Динамичното се състои в това, че приемаме, че сме намерили цялата информация до $i-$та колона, това включва и подробна информация за всеки възможен профил на тази колона. След което искаме да намерим същата информация за $(i+1)-$ва колона. Същността на техниката е, като имаме подходящ профил, да намерим как преминаваме от един профил до друг (дали можем, по колко начина и т.н.) и така да направим този преход от $i-$та в $(i+1)-$ва колона "автоматизирано" чрез умножение с матрица. По този начин намирането на целия отговор за таблицата с $m$ колони ще става с повдигане на матрица в степен.

Ще разгледаме една лесна задача, с която ще покажем нагледно техниката. Нека имаме таблица $n$x$m$, която искаме да оцветим в черно и бяло, така че да няма две съседни (по страна) черни клетки. Търсим по колко начина може да стане това. Нека фиксираме конкретни стойности: $n=m=2$. Тогава имаме следните 7 възможности:

За да подходим в стила на динамичното програмиране, идеята ще е да намерим броя начини за оцветяване на първите $i+1$ колони, след като вече знаем броя начини за първите $i$ колони. В общия случай няма как директно да го направим. Затова трябва да намерим необходимата информация, която да ни позволи това. В тази задача профилът е ясен - за всяка колона е достатъчно да знаем кои клетки сме оцветили в бяло и кои в черно, т.е. профилът е просто битова маска на оцветяването на дадена колона. Тази информация е еднотипна за всяка колона. Очевидно като знаем оцветяването на последната колона, знаем какви са валидните възможности за оцветяването на следващата колона. Това показва, че избраният профил е подходящ за задачата - можем да минаваме от един профил към друг. Всъщност така направихме първата стъпка за тази техника - да намерим подходящ профил. Един профил е подходящ, ако в него се включват всички възможности и може да се минава от един профил в друг без значение за кой номер на колона става дума. След като намерим подходящ профил намираме валидните профили и ги номерираме. За да е валиден даден профил, не трябва да има две съседни черни клетки в него. При два реда имаме три валидни профила от общо 4 възможни:

Стейтът на динамичното е $dp[$брой колони$][$номер на профила на последната колона$]$, като в него пазим броя валидни оцветявания. Базовите стойности са: $dp[1][0]=dp[1][1]=dp[1][2]=1$ (...понякога не всички профили са валидни за начални). За да сметнем стойностите при две колони е достатъчно да видим кои профили са съвместими. Написано подробно:

• $dp[2][0]=1*dp[1][0]+$ $1*dp[1][1]+1*dp[1][2]=3$
• $dp[2][1]=1*dp[1][0]+$ $0*dp[1][1]+1*dp[1][2]=2$
• $dp[2][2]=1*dp[1][0]+$ $1*dp[1][1]+0*dp[1][2]=2$

Всъщност едниствените несъвместими профили като ляв и десен са номер 1 със себе си и номер 2 със себе си. Може да се провери, че тези числа съответстват на разписването в случая $2$x$2$ по-горе. От друга страна горните формули са същите за получаване на бройките при 3 колони от тези за 2, при 4 колони от тези за 3 и т.н. Така в общия случай за $m$ колони при два реда е вярно:

• $dp[m][0]=1*dp[m-1][0]+$ $1*dp[m-1][1]+1*dp[m-1][2]$
• $dp[m][1]=1*dp[m-1][0]+$ $0*dp[m-1][1]+1*dp[m-1][2]$
• $dp[m][2]=1*dp[m-1][0]+$ $1*dp[m-1][1]+0*dp[m-1][2]$

Тази сметка може да се изрази и чрез матрично умножениe по следния начин: $\begin{pmatrix}dp[m-1][0] & dp[m-1][1] & dp[m-1][2]\end{pmatrix}*T=$ $\begin{pmatrix}dp[m][0] & dp[m][1] & dp[m][2]\end{pmatrix}$, където $T$ се нарича матрица на прехода между профилите. В нашия случай при два реда - $T=\begin{pmatrix}1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{pmatrix}$. Всъщност числата в колоните с индекси 0, 1 и 2 са коефициентите при смятането на $dp[m][0], dp[m][1]$ и $dp[m][2]$.

Забележете, че матрицата на прехода зависи от броя редове в задачата. Горна оценка за големината на $T$ е $2^n$ x $2^n$. При малко по-точен анализ, лесно може да се забележи, че броят валидни профили в зависимост от броя редове образуват редицата на Фибоначи или при $n$ реда, броят е $F_{n+2}$. Като вземем предвид, че $F_{n} \approx \varphi^n$, то големината на $T$ пак е експоненциална спрямо $n$: $\varphi^{n+2}$ x $\varphi^{n+2}$ (...известно още и като златното сечение - $\varphi \approx 1.618$). Затова искаме малък брой на редовете, иначе този подход е неприложим.

Следният код намира профилите и матрицата на прехода $T$:

Нека означим матрицата с началните стойности с $B$, т.е. $B=\begin{pmatrix}dp[1][0] & dp[1][1] & ... & dp[1][k-1]\end{pmatrix}$$=\begin{pmatrix}1 & 1 & ... & 1\end{pmatrix}$, защото в нашата задача всички профили са възможни за начални. Вече обосновахме, че за да смятаме стойностите, като добавим още една колона, е достатъчно да умножим с матрицата на прехода $T$. Това означава, че за да стигнем до $m$ колони, трябва да сметнем $B*\underbrace{T*T*...*T}_\text{$m-1$ на брой}$. Без да ползваме техниката динамично по профил тази задача бихме я решили, като последователно смятахме динамичните за 1 колона, 2 колони и т.н., което съответства на следното смятане с матрици: $B*T, (B*T)*T, ...$. Ако смятаме по този начин, сложността ще е $O(m*2^{2n})$, което е неприложимо за големи $m$. Но матричното умножение е асоциативно, което означава, че $B*\underbrace{T*T*...*T}_\text{$m-1$ на брой}=$$B*(T*T*...*T)=B*T^{m-1}$. Така първо ще сметнем $T^{m-1}$. Разбира се, ако го правим по наивния начин ще получим ужасна сложност $O(m*2^{3n})$, но можем да се възползваме от бързото повдигане в степен и така да паднем до $O(\log{m}*2^{3n})$. Нека означим $T^{m-1}=R$. След като сме сметнали $R$, остава лявото умножение с $B$, за да получим $\begin{pmatrix}dp[m][0] & dp[m][1] & ... & dp[m][k-1]\end{pmatrix}$, но понеже имаме само единици за базови стойности, то $dp[m][p]=\sum\limits_{i=0}^{k-1} R[i][p]$. Всъщност отговорът на задачата е $\sum\limits_{p=0}^{k-1} dp[m][p]$ или се получава сумата на числата в матрицата $R$ - $\sum\limits_{b=0}^{k-1} \sum\limits_{e=0}^{k-1} R[b][e]$.

Този резултат можехме да получим и по друг начин, който е по-ценен за осмислянето на умножението на матриците на прехода. Можем да кажем, че всъщност $T[l][r]$ е броят валидни оцветяване на 2 колони, при които първата е с профил $l$, а втората е с профил $r$. Това означава, че от своя страна $T^2[l][r]$ ще е броят валидни оцветяване на 3 колони, при които първата е в профил $l$, а последната е с профил $r$. Така ако погледнем $T^{m-1}$, номерът на реда съответства на профил на първата колона, а номерът на стълба - на профил на последна колона. Затова при произволна задача, за да намерим крайният отговор е достатъчно да съберем числата на редовете с валиден профил за начален и колоните с валиден профил за краен! В разглежданата задача всички профили са валидни за начални и крайни, затова и се получава, че събираме всичките числа в $T^{m-1}=R$. Предоставяме код, където при вече намерена матрица на прехода, намираме и броят валидни оцветявания на таблица $n$x$m$.

В следващия интерактивен пример могат да се въвеждат различни стойности за размерите на таблицата и да се пресмятат матриците $T$ и $T^{m-1}$. Също така се показват номерираните профили в реда, в който са и матриците, както и крайният отговор за съответните размери на таблицата. Максималната позволена стойност за $n$ e 3. Всички сметки се извършват по модул 100!

Последно ще кажем, че не винаги този подход при динамичното по профил е най-удачен, нещата зависят от конкретните ограничения. Ако няма малко измерение, то $O(2^{3n})$ или най-общо казано сложността за извършване на умножението на матрици при намиране на $T^2$, може да е твърде голяма. Тогава ако все пак няма много голямо измерение на таблицата, най-подходящо е стандартното намиране на динамичното, което вече описахме (със сложност $O(m*2^{2n})$ за нашата задача). Въпреки това част от подходите са добри практики - намирането на валидните профили, както и за всеки профил с кои и по колко начина е съвместим. Така стандартният начин се забързва малко повече.

Една доста известна задача е за броя начини да се покрие таблица $n$x$m$ с домина (...правоъгълни плочки с размери 1х2). БОО (...без ограничение на общността) $n \le m$. Тази задача има разнообразни решения. Стандартното решение с динамично с маска на последния стълб е със сложност $O(m*2^{2n})$. То обаче е по-бавно, а може би и по-тежко за писане, от решението с плъзгаща се битова маска, което има сложност $O(nm*2^n)$ (...може да разгледатe това решение в темата за динамично по подмножества). Сега ще разгледаме решение в стила на динамично по профил, което ще е със сложност $O(\log{m}*2^{3n})$. То ще е удачното, когато броя редове е малък до 6-7, иначе най-доброто би било динамичното с плъзгаща се битова маска.

Има различни начини за съставяне на профил. Най-лесният е да въведем три състояния за всяка клетка в колоната - покрита от вертикално домино, покрита от хоризонтално домино от предната колона или покрита от хоризонтално домино, отиващо в следващата колона. То обаче не е най-оптималното и ще доведе до много профили. По-оптимални варианти са следните. Един вариант е да оставяме празни клетки в колоната, които да бъдат попълнени при добавяне на следващата колона, а друг е да слагаме хоризонтални домина, които да "стърчат" от последната колона. Ще разгледаме втората възможност. Както в предната задача, ще използваме битова маска за кодиране на конфигурациите. Бит със стойност 1 ще означава, че сме поставили хоризонтално домино в тази клетка, което стърчи към следващата колона. Ако стойността е 0, това ще означава, че клетката е покрита с вертикално домино или хоризонтално, което започва от предишната колона. На пръв поглед може да изглежда, че този профил не винаги е еднозначен - когато имаме 0, не е напълно ясно дали клетката е покрита с вертикално или хоризонтално домино. Обаче ако разгледаме комбиниране на профили на лява и дясна колона, то при дясната колона нулите стават еднозначни - ако са покрити с хоризонтално домино от предишната колона, то при лявата колона, на съответното място, трябва да имаме бит 1 (за стърчащо домино), иначе са покрити с вертикално домино. За да стане по-ясна тази концепция е предоставен интерактивен пример, където могат да се въвеждат битови маски на профилите на лява и дясна колона и да се види нагледно как се покрива дясната колона, ако са съвместими профилите. Редовете са най-много 5.

Оказва се, че всички профили са валидни. Сега да изясним кога два профила са съвместими. Първото условие е на всеки бит 1 в левия профил да съответства бит 0 в десния профил, защото този бит е означавал стърчащо домино от лявата колона и то трябва да завършва на това място в десния профил. Останалите битове в левия профил са нули и съответните клетки трябва вече да са коректно покрити (без значение десния профил), така че при тях няма допълнителни условия. За десния профил знаем, че битовете 1 означават стърчащи домина, освен това част от нулите (съседни на бит 1 в левия профил) са покрити от хоризонтални домина, почващи в лявата колона. Всички останали нулеви битове трябва да са за вертикални домина! Така че второто условие е точно това - групите нули в десния профил, оградени от хоризонтални домина, да са четен брой, за да могат да се покрият с вертикални. Ето код, който намира матрицата на прехода $T$ за този профил:

Тук не всички профили са валидни за начални. Единствените хоризонтални домина в първата колона са стърчащи, което означава, че всички нули са покрити само от вертикални домина. Така че валидни начални профили са тези, при които всички поредици от нули са с четна големина. От друга страна в последната колона, хоризонталните домина трябва да започват от предходната колона. Това означава, че само профилът с маска 0 е валиден за краен. Като имаме матрицата на прехода, трябва да направим бързото повдигане в степен, което показахме, и да намерим $T^{m-1}$. За крайният отговор трябва да съберем числата от първата колона (тази с индекс 0, съответстваща на профил 0) на редовете с валиден начален профил.