Programowanie dynamiczne (ang. dynamic programming, DP) to technika optymalizacji, która polega na rozbijaniu problemu na mniejsze, nakładające się podproblemy, a następnie przechowywaniu ich wyników, aby uniknąć ponownego obliczania tych samych wartości. Dzięki temu można znacząco przyspieszyć działanie algorytmów.
Kiedy stosować programowanie dynamiczne?
Programowanie dynamiczne jest skuteczne, gdy:
- Problem można podzielić na mniejsze, podobne podproblemy.
- Podproblemy się nakładają, tzn. są takie same podproblemy, które pojawiają się wielokrotnie.
- Problem ma strukturę optymalnej podstruktury, co oznacza, że optymalne rozwiązanie można zbudować z optymalnych rozwiązań jego podproblemów.
Typowe przykłady problemów, które można rozwiązać przy użyciu programowania dynamicznego, to: problem plecakowy, ciąg Fibonacciego, problem najdłuższego wspólnego podciągu, i wiele innych.
Metody programowania dynamicznego
Programowanie dynamiczne można podzielić na dwa podejścia:
- Memoizacja (ang. memoization) – podejście od góry do dołu, polega na rozwiązywaniu problemu rekurencyjnie i zapamiętywaniu wyników podproblemów.
- Tablicowanie (ang. tabulation) – podejście od dołu do góry, polega na budowaniu rozwiązania od najmniejszych podproblemów do rozwiązania głównego problemu, zapisując wyniki w tabeli.
Przykład: Ciąg Fibonacciego
Zacznijmy od prostego przykładu, jakim jest obliczanie wartości w ciągu Fibonacciego. Każda liczba w tym ciągu to suma dwóch poprzednich liczb, czyli:
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2), dlan >= 2
Tradycyjna wersja rekurencyjna
Powyższy kod jest prosty, ale bardzo nieefektywny, ponieważ oblicza te same wartości wielokrotnie. Jego złożoność czasowa wynosi O(2^n).
Użycie memoizacji
Dzięki przechowywaniu wyników obliczeń w słowniku memo, złożoność czasowa tego rozwiązania spada do O(n).
Użycie tablicowania
W podejściu od dołu do góry tworzymy tablicę dp, która przechowuje wartości od F(0) do F(n). Każda wartość jest obliczana tylko raz, co również daje złożoność O(n).
Inne przykłady problemów z DP
Problem plecakowy (Knapsack Problem)
Załóżmy, że mamy plecak o określonej pojemności W, a do wyboru kilka przedmiotów, każdy z wagą i wartością. Celem jest maksymalizacja wartości, którą możemy zmieścić w plecaku, nie przekraczając jego pojemności.
Różnice Między Metodą Zachłanną a Programowaniem Dynamicznym
| Cecha | Metoda Zachłanna | Programowanie Dynamiczne |
|---|---|---|
| Podejście | Podejmowanie lokalnie najlepszych decyzji. | Rozbijanie problemu na mniejsze, nakładające się podproblemy. |
| Zastosowanie | Gdy można udowodnić, że lokalne wybory są globalnie optymalne. | Gdy problem ma nakładające się podproblemy i optymalną podstrukturę. |
| Struktura problemu | Problem z właściwością zachłanności. | Problem z optymalną podstrukturą. |
| Przechowywanie wyników | Nie przechowuje wcześniejszych wyników. | Przechowuje wyniki podproblemów, aby uniknąć ich ponownego liczenia. |
| Złożoność | Zazwyczaj prostsze i szybsze algorytmy. | Często bardziej złożone, ale optymalniejsze czasowo dla dużych problemów. |
Podsumowanie
Programowanie dynamiczne jest potężnym narzędziem, które pozwala rozwiązywać złożone problemy optymalizacyjne w efektywny sposób. W Pythonie możemy łatwo wykorzystać zarówno memoizację, jak i tablicowanie, dzięki wbudowanym struktury danych jak słowniki i listy. Kiedy napotykasz problem, który można podzielić na mniejsze podproblemy, które się powtarzają, rozważ zastosowanie programowania dynamicznego, aby poprawić efektywność rozwiązania.
Was this helpful?
0 / 0