Rozwiązaniem danego problemu często jest kombinacja rozwiązań podproblemów, na które można problem rozłożyć. Natomiast nie od razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu różnych dekompozycji. W sytuacji, gdy nie wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie mielibyśmy wiele wyborów i w sumie złożoność mogłaby być wykładnicza.
W takich sytuacjach stosujemy metodę zwaną programowaniem dynamicznym. Metoda ta, z grubsza biorąc, wygląda następująco: Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest wielomianowa, to zamiast korzystać z rekursji możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od "mniejszych" podproblemów do "większych". Rozmiary problemów muszą być odpowiednio zdefiniowane, nie powinno być zależności cyklicznej.
Wartości obliczone dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można rozbić dany problem, wartość problemu obliczamy korzystając z wartości zapamiętanych w tablicy.
Najistotniejsze jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie większy niż zbiór podproblemów będących częściami jednego optymalnego rozwiązania.
Spróbujmy skonstruować wielomianowy algorytm dla problemu minimalnego sklejania sąsiadów korzystając z programowania dynamicznego. Jeśli mamy dany ciąg \( p_1,p_2, \ldots p_n \), to w tym przypadku podproblem można utożsamić z pewnym przedziałem \( [i..j] \). Niech \( wynik[i,j] \) będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu \( (p_i,p_{i+1}, \ldots p_j) \);
oznaczmy ponadto
\( \sigma_{i,j}\ =\ \sum_{k=i}^j\ p_k \)
Algorytm Optymalne-Sklejanie-Sąsiadow
for i:=1 to n do wynik[i,i]:=0; for j:=2 to n do for i:=j-1 downto 1 do wynik[i,j] := min(i <= k < j) (wynik[i,k]+wynik[k+1,j]+sigma[i,j]) return wynik[1,n];
W algorytmie zasadniczą instrukcję
\( wynik[i,j] := \min_{i \le k < j}\ (wynik[i,k]+wynik[k+1,j]+\sigma_{i,j}) \)
można wykonywać w dowolnym przyzwoitym porządku ze względu na (i,j) (na przykład po przekątnych, zaczynając od głównej przekątnej). Przyzwoitość polega na tym, że jest już ostatecznie policzone to, z czego w danym momencie korzystamy.
Algorytm ma złożoność czasową \( O(n^3) \) i jest to "typowa" złożoność algorytmów tego typu. Duża złożoność wynika stąd, że liczymy wartości dla mnóstwa podproblemów, które mogą być zupełnie nieistotne z punktu widzenia optymalnego rozwiązania.
Problem sklejania sąsiadów można rozwiązać inaczej, modyfikując w sposób nietrywialny algorytm Optymalne-Sklejanie-Par. W algorytmie tym instrukcję
zastąp dwa najmniejsze elementy \( a,b \) przez \( a+b \)
zamieńmy na:
zastąp dwa sąsiednie elementy \( a,b \) o minimalnej sumie przez \( a+b \)
przesuń \( a+b \) przed najbliższy na prawo (w ciągu) element \( c \) większy od \( a+b \)
(na koniec ciągu, jeśli takiego \( c \) nie ma)
Otrzymany algorytm (wersja algorytmu Garsia-Wachsa) liczy koszt minimalnego sklejania sąsiadów. Jest to przykład pozornie prostego algorytmu, dla którego odpowiedź na pytanie, "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza zakres tego kursu. Pozostawiamy jako ćwiczenie implementację tego algorytmu w czasie \( O(n \log n) \), przy założeniu, że jest on poprawny. Jeśli liczby \( p_i \) są liczbami naturalnymi z przedziału \( [1..n] \), to istnieje nawet (bardzo trudna) implementacja w czasie liniowym.