Dynamiczne programowanie jest potężną techniką, która pozwala rozwiązywać różne rodzaje problemów w czasie, dla których podejście wymagałoby czasu wykładniczego. Niektóre znane algorytmy programowania dynamicznego to unix diff dla porównywania dwóch plików, Bellman – Ford do określenia najkrótszych tras w sieciach, TeX (przodek LaTeXa) i WASP – czyli wygrywający i przewidujący wynik. Podstawową ideą programowania dynamicznego jest unikanie powtarzania pracy poprzez zapamiętywanie częściowych wyników i ta koncepcja znajduje zastosowanie w wielu sytuacjach życiowych.
Programowanie dynamiczne to w zasadzie rekursja plus… użycie zdrowego rozsądku. Oznacza to, że rekurencja pozwala wyrazić wartość funkcji pod względem innych wartości tej funkcji. Tam, gdzie zdrowy rozsądek podpowiada, że zaimplementowanie swojej funkcji w taki sposób, że rekursywne rozmowy zostaną wykonane z wyprzedzeniem i będą przechowywane dla łatwego dostępu, przyspieszy to program. To właśnie nazywamy „memoryzacją” – a więc zapamiętywaniem wyników niektórych konkretnych stanów, które następnie mogą być później wykorzystane do rozwiązywania innych pod-problemów. Za programowaniem dynamicznym przemawia fakt, że zajmujemy się przestrzenią na czas, tzn.
Zamiast obliczać wszystkie stany zajmujące dużo czasu, ale bez przestrzeni, zajmujemy miejsce, aby przechowywać wyniki wszystkich pod-problemów, aby zaoszczędzić sobie czas później. W kodzie rekursywnym wiele wartości jest ponownie obliczanych wielokrotnie. Ale można zrobić to dobrze z obliczaniem każdej unikalnej ilości tylko jeden raz. Większość problemów związanych z programowaniem dynamicznym można podzielić na dwa typy – na problemy z optymalizacją oraz na problemy kombinatoryczne. Problemy z optymalizacją wymagają wyboru możliwego rozwiązania, tak aby wartość wymaganej funkcji była zminimalizowana lub zmaksymalizowana.
Kombinatoryczne problemy oczekują od nas natomiast, abyśmy dowiedzieli się, ile jest sposobów na zrobienie czegoś, lub prawdopodobieństwo wystąpienia jakiegoś konkretnego zdarzenia. Każdy problem z programowaniem dynamicznym ma schemat, którego należy przestrzegać. Po pierwsze, należy pokazać, że problem można podzielić na optymalne pod-problemy. Następnie, rekursywnie określić wartość rozwiązania, wyrażając je w kategoriach optymalnych rozwiązań dla mniejszych pod-problemów. Kolejny krok to obliczenie wartości optymalnego rozwiązania w trybie bottom-up i, finalnie, skonstruowanie optymalnego rozwiązania z wyliczonych informacji.
Memoryzacja jest bardzo łatwa do zakodowania i może być pierwszą linią podejścia przez jakiś czas. Jednak dzięki programowaniu dynamicznemu nie ryzykuje się nadmiaru przestrzeni stosów, a kończy z dużą swobodą, kiedy można wyrzucać obliczenia. Minusem jest to, że konieczne jest wymyślenie rozwiązania, które zadziała. Można myśleć o programowaniu dynamicznym jako algorytmie wypełniania tabel – znamy obliczenia, które musimy wykonać, więc wybieramy najlepszą kolejność ich wykonania i ignorujemy te, których nie musimy wypełniać.
Aby przekształcić funkcję backtrack ze złożonością czasową w rozwiązanie do tworzenia notatek o złożoności czasowej, użyjemy małej sztuczki, która nie wymaga prawie żadnego myślenia. Istnieją bowiem tylko różne argumenty, z którymi można wywoływać naszą funkcję. Innymi słowy, istnieją tylko różne rzeczy, które możemy obliczyć. Skąd zatem bierze się złożoność i co to jest obliczenie? Odpowiedź jest następująca: wykładnicza złożoność czasu wynika z powtarzanej rekurencji i z tego powodu wielokrotnie wylicza te same wartości.
Jeśli uruchomimy jakiś dowolny kod dla dowolnej tablicy, po czym obliczymy, ile razy funkcja nazywała się wyznaczonymi argumentami, otrzymamy taki, a nie inny, numer. Wielokrotne obliczanie tej samej odpowiedzi byłoby po prostu ogromną stratą czasu. Dlatego powinniśmy poprawić zapamiętanie wartości po ich obliczeniu i za każdym razem, gdy funkcja poprosi o już zapamiętaną wartość, nie będziemy musieli ponownie uruchamiać całej rekursji.
Jeśli zatem zauważymy, że problem można rozwiązać za pomocą dynamicznego programowania, spróbujmy utworzyć funkcję backtrack, która obliczy poprawną odpowiedź. Starajmy się unikać zbędnych argumentów, minimalizujmy zakres możliwych wartości argumentów funkcji, a także spróbujmy zoptymalizować złożoność czasową jednego wywołania funkcji (pamiętajmy, że możemy traktować wywołania rekurencyjne tak, jakby działały w czasie rzeczywistym). Na koniec możemy zapamiętać wartości i nie liczyć ich dwukrotnie.
