Lekcja 8. Programowanie dynamiczne — rozwiązywanie problemów sprytniej
Trudny / egzaminacyjnyPo co się tego uczymy?
W poprzedniej lekcji widziałeś, że naiwna rekurencja dla ciągu Fibonacciego liczy te same wartości WIELOKROTNIE — dla fib(40) program mógłby liczyć całymi minutami. Programowanie dynamiczne rozwiązuje ten problem, zapamiętując wyniki — i przyspiesza obliczenia nawet o kilkaset razy. To jedna z najważniejszych technik optymalizacyjnych na maturze rozszerzonej.
Teoria
Problem z naiwną rekurencją — fib(40) liczony "na piechotę" (jak w poprzedniej lekcji) ma złożoność O(2ⁿ) — WYKŁADNICZĄ, bo drzewo wywołań liczy TE SAME wartości wielokrotnie (np. fib(3) liczone dwa razy, fib(2) trzy razy — a dla fib(40) to miliardy powtórzeń).
Programowanie dynamiczne to sposób rozwiązywania problemów przez: (1) rozłożenie problemu na mniejsze podproblemy, (2) ZAPAMIĘTANIE wyników podproblemów (żeby nie liczyć ich ponownie), (3) złożenie rozwiązania całego problemu z rozwiązań podproblemów. To NIE jest technika o "dynamicznych danych" — to sztuka SPRYTNEGO ZAPAMIĘTYWANIA wyników.
Memoizacja to konkretna technika: przed obliczeniem wyniku SPRAWDZASZ, czy już go obliczyłeś. Jeśli tak — zwracasz zapamiętany wynik (bardzo szybko). Jeśli nie — obliczasz, zapamiętujesz i zwracasz. To jak notes: zanim rozwiążesz zadanie, sprawdzasz, czy nie rozwiązałeś go już wcześniej.
Trzy podejścia do programowania dynamicznego:
- A) Memoizacja (top-down) — rozwiązujesz duży problem, rozkładając go rekurencyjnie na mniejsze, zapamiętując wyniki w słowniku. Zalety: intuicyjne, naturalne dla rekurencji. Wady: może przepełnić stos dla bardzo dużych n.
- B) Tabulacja (bottom-up) — zaczynasz od NAJPROSTSZYCH podproblemów i budujesz się w górę (tablicą, bez rekurencji). Zalety: brak ryzyka przepełnienia stosu, bardziej efektywna pamięciowo. Wady: trzeba przemyśleć, od czego zacząć.
- C) Optymalizacja przestrzeni — jeśli potrzebujesz tylko OSTATNICH wartości (jak w Fibonaccim, gdzie liczy się tylko 2 poprzednie), możesz pominąć całą tablicę i trzymać tylko potrzebne zmienne. Złożoność: O(n) czasu, O(1) pamięci — idealne!
Kiedy problem NADAJE SIĘ do programowania dynamicznego — musi mieć: (1) optymalną podstrukturę — optymalne rozwiązanie dużego problemu zbudowane jest z optymalnych rozwiązań podproblemów, (2) nakładające się podproblemy — te same podproblemy pojawiają się wielokrotnie. Przykłady, gdzie DZIAŁA: Fibonacci, problem plecakowy, najkrótsza ścieżka. Gdzie NIE działa: szukanie liczby pierwszej (brak optymalnej podstruktury), sortowanie (brak nakładających się podproblemów).
Problem plecakowy (0/1 Knapsack) — masz plecak o pojemności W kg i n przedmiotów, każdy z wagą i wartością; chcesz zabrać maksymalną WARTOŚĆ, nie przekraczając wagi. Rozwiązanie tabulacją buduje tablicę dp[i][w] = maksymalna wartość z i pierwszych przedmiotów przy dostępnej wadze w — złożoność O(n × W), znacznie lepsza niż sprawdzanie WSZYSTKICH możliwych podzbiorów (O(2ⁿ)).
Schemat
DRZEWO WYWOŁAŃ fib(5) - naiwna rekurencja (POWTÓRZENIA!):
fib(5)
/
fib(4) fib(3)
/ /
fib(3) fib(2) fib(2) fib(1)
/ / /
fib(2) fib(1) fib(1) fib(0) ...
fib(3) liczymy 2 razy, fib(2) aż 3 razy!
Dla fib(40): MILIARDY powtórzeń → O(2^n)
Z MEMOIZACJĄ - każdy podproblem liczony TYLKO RAZ:
fib(5) → fib(4) → fib(3) → fib(2) → fib(1)=1, fib(0)=0
↓ zapamiętane w słowniku
gdy potrzebne ponownie → odczyt z pamięci (natychmiastowo!)
Złożoność: O(n) zamiast O(2^n)
Przykład z życia
Nawigacja GPS obliczająca najkrótszą trasę między dwoma miastami NIE liczy od zera odległości dla każdej możliwej kombinacji dróg — zapamiętuje najkrótsze odległości do POŚREDNICH punktów i wykorzystuje je do zbudowania ostatecznej trasy. To dokładnie idea programowania dynamicznego: rozwiąż mniejsze podproblemy raz, zapamiętaj, użyj wielokrotnie.
fibonacci_dynamiczne.py
# Naiwna rekurencja - liczy te same wartości WIELOKROTNIE
def fib_naiwny(n):
if n <= 1:
return n
return fib_naiwny(n-1) + fib_naiwny(n-2)
print(fib_naiwny(5)) # 5 (szybko)
# print(fib_naiwny(40)) # zajmie wiele sekund! O(2^n)
# Programowanie dynamiczne - memoizacja (top-down)
def fib_memo(n, cache=None):
if cache is None:
cache = {}
if n in cache:
return cache[n] # Znalazłem! Zwracam z pamięci
if n <= 1:
return n
cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache) # licz i zapamiętaj
return cache[n]
print(fib_memo(40)) # Natychmiastowo! O(n)
# Tabulacja (bottom-up) - budujemy od najprostszych podproblemów w górę
def fib_tabela(n):
if n <= 1:
return n
tablica = [0] * (n + 1)
tablica[1] = 1
for i in range(2, n + 1):
tablica[i] = tablica[i-1] + tablica[i-2]
return tablica[n]
print(fib_tabela(40)) # Szybko i bezpiecznie, O(n)
# Optymalizacja przestrzeni - potrzebujemy tylko dwóch ostatnich wartości
def fib_optymalna(n):
if n <= 1:
return n
poprzednia, obecna = 0, 1
for _ in range(2, n + 1):
poprzednia, obecna = obecna, poprzednia + obecna
return obecna
print(fib_optymalna(40)) # O(n) czasu, O(1) pamięci!plecak_i_monety_dynamiczne.py
# Problem plecakowy 0/1 - programowanie dynamiczne (tabulacja)
def plecak(waga_max, wagi, wartosci, n):
# Tablica: dp[i][w] = maksymalna wartość z i przedmiotów przy wadze w
dp = [[0] * (waga_max + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(waga_max + 1):
nie_biore = dp[i-1][w] # Nie biorę przedmiotu
biore = 0 # Biorę przedmiot (jeśli się mieści)
if wagi[i-1] <= w:
biore = wartosci[i-1] + dp[i-1][w - wagi[i-1]]
dp[i][w] = max(nie_biore, biore) # Wybieram lepsze rozwiązanie
return dp[n][waga_max]
wagi = [2, 3, 4]
wartosci = [60, 50, 40]
wynik = plecak(5, wagi, wartosci, 3)
print(f"Maksymalna wartość: {wynik} zł") # 110 (złoto 2kg/60zł + srebro 3kg/50zł)
# Najmniejsza liczba monet - programowanie dynamiczne
def najmniej_monet(kwota, monety):
dp = [float('inf')] * (kwota + 1)
dp[0] = 0 # Na kwotę 0 potrzeba 0 monet
for i in range(1, kwota + 1):
for moneta in monety:
if moneta <= i:
dp[i] = min(dp[i], dp[i - moneta] + 1)
return dp[kwota]
monety = [1, 5, 10]
wynik = najmniej_monet(27, monety)
print(f"Minimalna liczba monet: {wynik}") # 5 (10+10+5+1+1 = 27)Komentarz i wyjaśnienie kodu
W fib_memo() słownik cache pełni rolę "notatnika" — if n in cache: return cache[n] to KLUCZOWA linia: zanim cokolwiek policzysz, sprawdzasz, czy wynik już istnieje.
W plecak() dla KAŻDEGO przedmiotu i KAŻDEJ możliwej wagi sprawdzamy DWIE opcje: nie brać przedmiotu (nie_biore = dp[i-1][w], czyli wynik BEZ tego przedmiotu) albo wziąć go, jeśli się mieści (biore) — i wybieramy WIĘKSZĄ wartość. To systematyczne sprawdzenie wszystkich decyzji "brać czy nie brać" jest znacznie szybsze niż próbowanie WSZYSTKICH 2ⁿ możliwych podzbiorów przedmiotów.
Zwróć uwagę na wynik najmniej_monet(27, [1,5,10]): minimalna liczba monet to 5 (10+10+5+1+1), NIE mniej — dla tych konkretnych nominałów nie da się wydać 27 zł mniejszą liczbą monet, co programowanie dynamiczne systematycznie sprawdza (w przeciwieństwie do "zgadywania" algorytmem zachłannym z poprzedniej lekcji).
Ćwiczenie samodzielne
Uruchom fib_naiwny(30) i zmierz czas wykonania (moduł time), a potem fib_memo(30) — porównaj różnicę. Następnie spróbuj fib_naiwny(40) (uzbrój się w cierpliwość) i fib_memo(40) (powinno być natychmiastowe).
Zadania do pracy własnej
Napisz trzy wersje funkcji Fibonacciego:
fib_naiwny(n)(zwykła rekurencja),fib_memo(n)(z memoizacją),fib_tabela(n)(tabulacja) — i porównaj czas działania dla n=35 (modułtime).Zmodyfikuj funkcję
plecak()tak, żeby oprócz maksymalnej wartości wypisywała też, KTÓRE przedmioty zostały wybrane (wskazówka: przeanalizuj tablicędp"wstecz", zaczynając oddp[n][waga_max]).Rozwiąż problem "najdłuższego wspólnego podciągu" (LCS) dla dwóch napisów metodą programowania dynamicznego: dla napisów
"ABCBDAB"i"BDCABA"znajdź najdłuższy wspólny podciąg znaków występujących w tej samej kolejności (niekoniecznie sąsiadująco). Zbuduj tablicędp[i][j]analogicznie do problemu plecakowego.
Typowe błędy
Używanie naiwnej rekurencji dla problemów z NAKŁADAJĄCYMI SIĘ podproblemami — bez zapamiętywania, złożoność rośnie WYKŁADNICZO, co dla n większego niż ok. 35-40 czyni program praktycznie bezużytecznym.
Zapominanie o warunku if n in cache PRZED obliczeniami w memoizacji — bez tego sprawdzenia funkcja nadal liczy wszystko od nowa, tracąc sens całej techniki.
Stosowanie programowania dynamicznego tam, gdzie problem NIE MA optymalnej podstruktury lub nakładających się podproblemów (np. sortowanie) — to niepotrzebne komplikowanie kodu bez żadnej korzyści w wydajności.
Nawiązanie do egzaminu zawodowego
Programowanie dynamiczne to jedna z najważniejszych technik na maturze rozszerzonej z informatyki — łączy rekurencję (z dwóch poprzednich lekcji) z systematycznym zapamiętywaniem wyników, rozwiązując problemy (jak plecak 0/1), gdzie proste podejście zachłanne (poprzednia lekcja) zawodzi. W kolejnych lekcjach poznasz kolejne struktury danych (stos i kolejka) używane m.in. właśnie w algorytmach dynamicznych i przeszukiwaniu grafów.