Programowanie dynamiczne — memoizacja i tabulacja wyjaśnione

Programowanie dynamiczne to sposób rozwiązywania problemów przez zapisywanie odpowiedzi dla mniejszych podproblemów i ponowne wykorzystywanie ich później. Sprawdza się wtedy, gdy te same podproblemy pojawiają się wielokrotnie, a pełne rozwiązanie można zbudować z tych mniejszych odpowiedzi.

Dwa główne style to memoizacja i tabulacja. Memoizacja zapisuje odpowiedzi podczas rozwiązania rekurencyjnego. Tabulacja wypełnia odpowiedzi w kolejności od dołu do góry, zwykle przy użyciu tablicy lub tabeli.

Kiedy programowanie dynamiczne działa

Programowanie dynamiczne jest przydatne, gdy spełnione są dwa warunki.

Po pierwsze, podproblemy nakładają się na siebie. Oznacza to, że ten sam wynik pośredni jest potrzebny więcej niż raz. Po drugie, większe odpowiedzi można budować z mniejszych w spójny sposób.

Jeśli te warunki nie są spełnione, przechowywanie starych wyników może zwiększać koszt pamięci bez większej korzyści.

Memoizacja a tabulacja

Memoizacja: przechowywanie od góry do dołu

Memoizacja zaczyna się od pomysłu rekurencyjnego. Gdy algorytm po raz pierwszy rozwiązuje podproblem, zapisuje wynik. Późniejsze wywołania wykorzystują zapisaną wartość zamiast liczyć ją ponownie.

Ten styl jest często łatwiejszy, gdy rekurencja jest jasna, ale kolejność wszystkich potrzebnych stanów nie jest oczywista.

Tabulacja: budowanie od dołu do góry

Tabulacja zaczyna od przypadków bazowych i wypełnia stany w takiej kolejności, aby potrzebne zależności były dostępne we właściwym momencie.

Ten styl jest często łatwiejszy, gdy znasz już przejrzystą kolejność iteracji i chcesz mieć bezpośrednią kontrolę nad tabelą.

Przykład programowania dynamicznego: Fibonacci

Ciąg Fibonacciego jest zdefiniowany przez

$$F(0) = 0, \quad F(1) = 1$$

oraz dla $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Zwykłe rozwiązanie rekurencyjne powtarza obliczenia. Na przykład obliczenie $F(5)$ wymaga $F(4)$ i $F(3)$, a potem obliczenie $F(4)$ znowu wymaga $F(3)$. To powtarzające się wywołanie $F(3)$ jest właśnie tym rodzajem marnowania pracy, który usuwa programowanie dynamiczne.

Memoizacja dla Fibonacciego

Przy memoizacji rekurencja pozostaje taka sama, ale każda wartość jest zapisywana po pierwszym obliczeniu.

Dla $F(5)$ użyteczna sekwencja wygląda tak:

• oblicz i zapisz $F(0)=0$
• oblicz i zapisz $F(1)=1$
• oblicz i zapisz $F(2)=1$
• oblicz i zapisz $F(3)=2$
• oblicz i zapisz $F(4)=3$
• oblicz i zapisz $F(5)=5$

Najważniejsze jest to, że każdy stan jest obliczany tylko raz. Późniejsze odwołania odczytują zapisaną wartość.

Tabulacja dla Fibonacciego

Przy tabulacji budujesz rozwiązanie od przypadków bazowych w górę:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Ta wersja wyraźnie pokazuje kolejność zależności: każda nowa wartość korzysta z wpisów, które są już znane.

Dlaczego programowanie dynamiczne może być szybsze

Jeśli problem ma tylko $k$ różnych stanów, które mają znaczenie, programowanie dynamiczne stara się rozwiązać każdy z tych $k$ stanów tylko raz. To może zamienić duże drzewo rekurencji w znacznie mniejsze obliczenie.

Dokładne przyspieszenie zależy od problemu. Programowanie dynamiczne nie jest automatycznie szybkie. Pomaga wtedy, gdy powtarzająca się praca jest rzeczywistą częścią pierwotnego rozwiązania.

Typowe błędy w programowaniu dynamicznym

Używanie go, gdy podproblemy się nie nakładają

Nie każdy problem rekurencyjny jest problemem programowania dynamicznego. Jeśli prawie każdy podproblem jest inny, zapisywanie wyników może nie oszczędzić dość pracy, by miało to znaczenie.

Złe zdefiniowanie stanu

Stan musi zawierać wszystkie informacje potrzebne do następnego kroku. Jeśli brakuje ważnych informacji, rekurencja może wyglądać poprawnie, ale dawać błędne odpowiedzi.

Błędne przypadki bazowe

Przypadki bazowe stanowią fundament całej metody. Jeśli wartości początkowe są błędne, każdy późniejszy stan zbudowany na ich podstawie też będzie błędny.

Wypełnianie tabeli w złej kolejności

Tabulacja działa tylko wtedy, gdy każdy stan jest wypełniany po stanach, od których zależy. Nawet poprawna rekurencja może zawieść, jeśli kolejność wypełniania jest zła.

Zakładanie, że programowanie dynamiczne zawsze oznacza optymalizację

Wiele znanych przykładów polega na maksymalizacji lub minimalizacji czegoś, ale programowanie dynamiczne stosuje się też do problemów zliczania i decyzyjnych. Prawdziwym sygnałem są podproblemy, które da się wykorzystać ponownie, a nie słowo „najlepszy”.

Gdzie używa się programowania dynamicznego

Programowanie dynamiczne pojawia się w takich problemach jak odległość edycyjna, najdłuższy wspólny podciąg, zliczanie ścieżek, optymalizacja typu plecakowego oraz niektóre ustawienia problemu najkrótszej ścieżki.

Gdy zastanawiasz się, czy warto go użyć, zadaj dwa pytania:

• czy mniejsze podproblemy się powtarzają?
• czy większą odpowiedź można zbudować z tych mniejszych odpowiedzi?

Jeśli na oba pytania odpowiedź brzmi tak, programowanie dynamiczne jest bardzo dobrym kandydatem.

Spróbuj podobnego problemu

Spróbuj własnej wersji z liczbą sposobów wejścia na $n$ stopni, jeśli każdy ruch to albo $1$ stopień, albo $2$ stopnie. Rekurencja jest prosta, powtarzające się podproblemy łatwo zauważyć i jest to dobry kolejny przykład po Fibonaccim.