Programowanie dynamiczne – rozwiązanie problemów sprytniej

Kiedy liczysz coś wiele razy, zapamiętaj, że już to liczyłeś

1. Wstęp: dwa sposoby na ten sam problem

Wyobraź sobie, że dostajesz zadanie z matematyki: oblicz Fibonacciego(5).

Pewnie myślisz: „Łatwe, po prostu użyj rekurencji!”

pythondef fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(5))  # 5

Działa! Ale teraz spróbuj: fib(40). Program… przestaje pracować. Czeka, czeka… a ty się zmieniasz w posąg.

Czemu? Bo rekurencja liczę setki tysięcy razy to samo.

Ale jest sprytniejszy sposób: zapamiętaj wyniki, które już obliczyłeś. Zamiast liczyć coś wiele razy, wylicz tylko raz i zapisz.

To właśnie programowanie dynamiczne — sposób na rozwiązywanie problemów przez:

Rozłożenie problemu na mniejsze podproblemy.
Zapamiętanie wyników podproblemów (by nie liczyć ich ponownie).
Złożenie rozwiązania całego problemu z rozwiązań podproblemów.

Zapamiętaj: Programowanie dynamiczne to nie o „dynamicznych danych”, tylko o sprytnym zapamiętywaniu wyników.

2. Problem Fibonacciego – dlaczego rekurencja nie wystarczy

Ciąg Fibonacciego: każda liczba to suma dwóch poprzednich.

textF(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
...

Rekurencja naiwna – liczenie tego samego wiele razy

pythondef 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!

Co się dzieje? Drzewo wywołań dla fib(5):

text                fib(5)
               /      \
            fib(4)      fib(3)
           /      \      /    \
        fib(3)  fib(2) fib(2) fib(1)
       /    \    /  \   /  \
    fib(2) fib(1) fib(1) fib(0) ...
    
Widzisz? fib(3) liczymy dwa razy, fib(2) trzy razy!
Dla fib(40) liczysz miliardy duplikatów.

Złożoność czasowa: O(2^n) — wykładnicza, a więc BARDZO wolna.

Programowanie dynamiczne – zapamiętaj wyniki

Ale jeśli zapamiętasz każdy wynik, liczysz każdy podproblem tylko raz.

pythondef fib_dynamiczny(n, pamiec=None):
    if pamiec is None:
        pamiec = {}
    
    # Sprawdź, czy już obliczyłem
    if n in pamiec:
        return pamiec[n]
    
    # Warunek bazowy
    if n <= 1:
        return n
    
    # Oblicz i zapamiętaj
    pamiec[n] = fib_dynamiczny(n-1, pamiec) + fib_dynamiczny(n-2, pamiec)
    return pamiec[n]

print(fib_dynamiczny(40))  # Natychmiastowo!

Złożoność czasowa: O(n) — liniowa, czyli 500 razy szybsza od naiwnej!

3. Czym jest memoizacja – czyli najważniejsza idea

Memoizacja to technika, w której:

Przed obliczeniem wyniku sprawdzasz, czy już go obliczyłeś.
Jeśli tak — zwracasz zapamiętany wynik (bardzo szybko).
Jeśli nie — obliczasz, zapamiętajesz i zwracasz.

To jak notes:

Zanim rozwiążesz zadanie, sprawdzasz, czy nie rozwiązałeś go już wcześniej.
Jeśli tak, czytasz notkę — gotowe!
Jeśli nie, rozwiązujesz, zapisujesz w nocie na przyszłość.

python# Słownik do zapamiętywania wyników
memo = {}

def fib_memo(n):
    if n in memo:
        return memo[n]  # Znalazłem! Zwracam z notatki
    
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n-1) + fib_memo(n-2)  # Liczymy i zapisujemy
    return memo[n]

print(fib_memo(100))  # Działa w ułamku sekundy!

4. Trzy podejścia do programowania dynamicznego

A) Memoizacja (top-down) – od góry na dół

Rozwiązujesz duży problem, rozkładając go na mniejsze.

pythondef fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

Zalety: Intuicyjne, naturalne dla rekurencji.
Wady: Może przepełnić stos dla bardzo dużych n.

B) Tabulacja (bottom-up) – od dołu na górę

Zaczynasz od najprostszych podproblemów i budujesz się w górę.

pythondef fib_tabla(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_tabla(40))  # Szybko i bezpiecznie

Zalety: Nie ma ryzyka przepełnienia stosu, bardziej efektywna pamięciowo.
Wady: Trzeba pomyśleć, od czego zacząć.

C) Optymalizacja przestrzeni – jeśli potrzebujesz tylko ostatnich wartości

Dla Fibonacciego potrzebujesz tylko dwóch poprzednich liczb:

pythondef 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(1) pamięci!

Złożoność: O(n) czasu, O(1) pamięci — idealne!

5. Praktyczny przykład: problem plecakowy (0/1 Knapsack)

Masz plecak o pojemności W kilogramów.
Masz n przedmiotów, każdy z wagą i wartością.
Chcesz zabrać maksymalną wartość, bez przekraczania wagi.

Przykład:

Plecak: 5 kg
Przedmioty:
- Złoto: 2 kg, 60 zł
- Srebro: 3 kg, 50 zł
- Miedź: 4 kg, 40 zł

Jakie wziąć? (To problem decyzyjny — bierzesz lub nie bierzesz każdy przedmiot)

Rozwiązanie: programowanie dynamiczne (tabulacja)

pythondef plecak(waga_max, wagi, wartosci, n):
    # Tablica: dp[i][w] = maksymalna wartość z i przedmiotów i wagą 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 biorę przedmiotu
            nie_biore = dp[i-1][w]
            
            # Biore przedmiot (jeśli się mieści)
            biore = 0
            if wagi[i-1] <= w:
                biore = wartosci[i-1] + dp[i-1][w - wagi[i-1]]
            
            # Wybieram lepsze rozwiązanie
            dp[i][w] = max(nie_biore, biore)
    
    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 + srebro)

Złożoność: O(n × W) — liniowa względem liczby przedmiotów i pojemności!

6. Kolejny przykład: najmniejsza liczba monet

Masz monety o nominałach: 1, 5, 10 zł.
Chcesz wydać kwotę K najmniejszą liczbą monet.

„Dla K = 27 zł:
Jeśli wybierzemy naiwnie (zawsze największą): 10 + 10 + 5 + 1 + 1 = 5 monet
Ale czy to najlepsze rozwiązanie? Programowanie dynamiczne pokaże nam właściwy wynik.”

Rozwiązanie: programowanie dynamiczne

pythondef najmniej_monet(kwota, monety):
    # dp[i] = najmniejsza liczba monet na kwotę i
    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}")  # 3 (10 + 10 + 5 + 1 + 1 = 27)

Złożoność: O(K × n) — bardzo efektywne!

7. Charakterystyka problemów, które rozwiązuje programowanie dynamiczne

Problem da się rozwiązać programowaniem dynamicznym, jeśli ma:

Optymalną podstrukturę — optymalne rozwiązanie dużego problemu zbudowane jest z optymalnych rozwiązań podproblemów.
Podproblemy się nakładają — te same podproblemy pojawiają się wielokrotnie.

Przykłady:

OK! Fibonacci — podproblemy się powtarzają
OK! Problem plecakowy — optymalne rozwiązanie dla 3 kg to część rozwiązania dla 5 kg
OK! Najkrótsza ścieżka — najkrótsza droga z A do C to część najkrótszej drogi z A do D
NO! Szukanie liczby pierwszej — nie ma optymalnej podstruktury
NO! Sortowanie — nie ma nakładających się podproblemów

8. Porównanie: rekurencja naiwna vs. programowanie dynamiczne

Aspekt	Rekurencja naiwna	Programowanie dynamiczne
Idea	Dziel problem rekurencyjnie	Pamiętaj wyniki podproblemów
Złożoność (Fib)	O(2^n) — bardzo wolna	O(n) — szybka
Pamięć	O(n) — głębokość stosu	O(n) — tablica wyników
Kod	Prosty	Bardziej złożony
Kiedy użyć	Małe problemy, < 30 elementów	Duże problemy, wiele podproblemów

9. Zadania dla ucznia

Zadanie 1 — Fibonacci

Napisz funkcje:

fib_naiwny(n) — zwykła rekurencja
fib_memo(n) — z memoizacją
fib_tablica(n) — tabulacja

Porównaj czas dla n = 35.

pythonimport time

def fib_naiwny(n):
    if n <= 1:
        return n
    return fib_naiwny(n-1) + fib_naiwny(n-2)

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

def fib_tablica(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Test
n = 35
start = time.time()
wynik1 = fib_naiwny(n)
czas1 = time.time() - start

start = time.time()
wynik2 = fib_memo(n)
czas2 = time.time() - start

start = time.time()
wynik3 = fib_tablica(n)
czas3 = time.time() - start

print(f"Naiwna: {wynik1}, czas: {czas1:.4f}s")
print(f"Memo: {wynik2}, czas: {czas2:.4f}s")
print(f"Tablica: {wynik3}, czas: {czas3:.4f}s")

10. Podsumowanie

Programowanie dynamiczne to potężna technika optymalizacyjna, która pozwala rozwiązywać problemy NP-trudne w rozsądnym czasie — pod warunkiem, że problem ma optymalną podstrukturę i nakładające się podproblemy. Umiejętność rozpoznawania takich problemów i wyboru między memoizacją a tabulacją to klucz do sukcesu na maturze z informatyki i w rzeczywistych algorytmach.

11. Do zapamiętania

Programowanie dynamiczne to sztuka rozpoznawania, co liczyłeś już wcześniej. > Jeśli coś powtarza się wiele razy — zapamiętaj to, a Twój program będzie > 500 razy szybszy.