Programowanie dynamiczne — pamiętaj, co policzyłeś

🎯 Po co Ci to?

Dwa razy obiecaliśmy lekarstwo: na wykładniczego Fibonacciego (4.3, 7.2) i na plecak (8.2). Czas dostarczyć. Pomysł jest rozbrajająco prosty — tak prosty, że jego wynalazca Richard Bellman ukrył go pod celowo mętną nazwą „programowanie dynamiczne", żeby brzmiało poważnie przed sponsorami z wojska (sam to przyznał we wspomnieniach; „programowanie" znaczyło wtedy „planowanie", nie kodowanie). Pomysł brzmi: skoro liczysz to samo wiele razy — zapisuj wyniki. Tyle. A z tej banalnej obserwacji wyrasta metoda, która łamie problemy nie do ruszenia zachłannością i nieosiągalne pełnym przeglądem.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • przyspieszyć rekurencję spamiętywaniem (memoizacją) — z wykładniczej do liniowej;
  • budować rozwiązania „od dołu": tabela podproblemów wypełniana po kolei;
  • rozwiązać wydawanie reszty dla DOWOLNEGO systemu monet — optymalnie.

🔁 Przypomnij sobie

Z 7.2: nachodzące podproblemy to trucizna rekurencji (fib(3) liczone wielokrotnie); z 4.3: iteracja z oknem; z 8.1: monety {1, 3, 4} i kwota 6.

📘 Wyjaśnienie

Krok 1: spamiętywanie (memoizacja). Weź naiwnego Fibonacciego i dołóż notes: zanim policzysz, sprawdź w notesie; po policzeniu — zapisz:

notes = {}                            # słownik: n → F(n); pusty na start

def fib(n):
    if n in notes:                    # już liczyłem? oddaj z notesu
        return notes[n]
    if n <= 2:
        return 1
    wynik = fib(n - 1) + fib(n - 2)
    notes[n] = wynik                  # zapisz na przyszłość
    return wynik

(Słownik {} to struktura „klucz → wartość" — szufladki podpisane dowolnymi etykietami; n in notes sprawdza, czy szufladka istnieje. Formalnie poznasz go w dziale 9 — tu wystarczy intuicja notesu.) Co się zmieniło? Każde fib(k) liczy się raz — drugie i kolejne wywołania trafiają w notes. Drzewo wywołań z 7.2, które puchło wykładniczo, zapada się do łańcucha: fib(50) to teraz ~50 obliczeń zamiast dwunastu miliardów. Jedna linijka „sprawdź notes" + jedna „zapisz" = zmiana klasy z $O(2^n)$ na $O(n)$. To jest najbardziej opłacalna transakcja w tej książce.

Krok 2: od dołu (tabela). Spamiętywanie zachowuje rekurencję i leczy ją notesem. Można też odwrotnie: wyrzucić rekurencję i budować notes po kolei, od najmniejszych podproblemów — bo przecież wiadomo, w jakiej kolejności będą potrzebne:

def fib_tabela(n):
    F = [0] * (n + 1)
    F[1] = F[2] = 1
    for i in range(3, n + 1):
        F[i] = F[i - 1] + F[i - 2]    # każdy wpis z dwóch wcześniejszych
    return F[n]

To ta sama idea co iteracja z oknem (4.3) — tyle że trzymamy całą tabelę, co za chwilę okaże się kluczowe: w trudniejszych problemach nie wiadomo z góry, które wcześniejsze wpisy będą potrzebne.

📐 DEFINICJA — programowanie dynamiczne: metoda rozwiązywania problemów o nachodzących podproblemach: zdefiniuj podproblemy, znajdź zależność (jak wynik podproblemu wynika z mniejszych), wypełniaj tabelę od najmniejszych do celu (albo rekurencyjnie ze spamiętywaniem).

Po ludzku: dziel i zwyciężaj dla problemów, w których kawałki się powtarzają — z notesem zamiast liczenia w kółko. Czym NIE jest: zachłannością. Dynamiczne rozważa wszystkie opcje każdej decyzji (i dlatego znajduje optimum), tylko robi to bez powtórek — spryt siedzi w niepowtarzaniu, nie w pomijaniu.

Popis: reszta w dowolnym systemie monet. Wróćmy do monet {1, 3, 4} i kwoty 6, na której poległa zachłanność (8.1). Podproblem: $M(k)$ = najmniejsza liczba monet na kwotę $k$. Zależność: ostatnia moneta to 1, 3 albo 4 — więc:

$$M(k) = 1 + \min\big(M(k-1),\ M(k-3),\ M(k-4)\big)$$

(bierzemy najlepszą z opcji „dołóż tę monetę do optymalnej reszty"). Baza: $M(0) = 0$. Tabela od dołu:

$k$ 0 1 2 3 4 5 6
$M(k)$ 0 1 2 1 1 2 2

$M(6) = 1 + \min(M(5), M(3), M(2)) = 1 + \min(2, 1, 2) = 2$ — dwie monety (3+3). Optimum, którego zachłanność nie widziała — znalezione mechanicznie, bez żadnego sprytu, samą sumiennością tabeli:

def reszta_optymalnie(kwota, nominaly):
    M = [0] + [float("inf")] * kwota          # inf = "jeszcze nie wiadomo jak"
    for k in range(1, kwota + 1):
        for n in nominaly:
            if n <= k and M[k - n] + 1 < M[k]:
                M[k] = M[k - n] + 1
    return M[kwota]

Koszt: kwota × liczba nominałów — dla kwoty 10 000 i 10 nominałów sto tysięcy operacji, mrugnięcie. Porównaj z $2^n$ pełnego przeglądu. Dynamiczne kupiło optymalność za pamięć na tabelę — znajomy handel (6.6: gwarancja za pamięć), tym razem w wersji, która zmienia niemożliwe w rutynę.

💭 Pomyśl: W tabeli $M$ siedzi liczba monet, ale nie widać, które monety wziąć. Jak odtworzyć skład optymalnej reszty z gotowej tabeli — bez liczenia od nowa?

Sprawdź odpowiedź

Idź od końca: stoisz na $k = 6$; sprawdź, która moneta „zrobiła" minimum — $M(6) = M(3) + 1$, więc ostatnia moneta to 3; skocz na $k = 3$; $M(3) = M(0) + 1$ — moneta 3; jesteś na zerze, koniec: reszta = {3, 3}. Tabela pamięta wartości optimum, a ścieżka po tabeli odtwarza decyzje. Ten manewr (odtwarzanie rozwiązania z tabeli) to standardowa druga część zadań z dynamicznego — i wróci w 8.4 przy drodze i podciągu.

⚠️ Uwaga, pułapka

Dynamiczne wymaga, żeby podproblemy dały się uporządkować (od mniejszych do większych) i żeby zależność korzystała tylko z wcześniejszych. Wypełnisz tabelę w złej kolejności — odczytasz inf albo śmieci z komórek, których jeszcze nie policzono. W reszta_optymalnie pętla po $k$ rośnie właśnie dlatego, że $M(k)$ sięga tylko wstecz ($k - n$). Zanim napiszesz pętlę, zadaj sobie rytualne pytanie: czego potrzebuje ta komórka i czy już to mam?

🛠️ Teraz Ty

Bez komputera: wypełnij tabelę $M$ dla monet {1, 5, 8} i kwoty 12 (zachłanność brała 8+1+1+1+1 — pięć monet; co mówi tabela?). Z komputerem: zaimplementuj reszta_optymalnie z odtwarzaniem składu monet; porównaj z zachłannością na systemie {1, 3, 4} dla kwot 1–20 — dla ilu kwot zachłanność się myli?

📐 Definicje tej lekcji

  • Spamiętywanie (memoizacja) — notes wyników przy rekurencji: sprawdź przed liczeniem, zapisz po; zmienia klasę przy nachodzących podproblemach.
  • Programowanie dynamiczne — podproblemy + zależność + tabela wypełniana od najmniejszych; optymalność bez powtórek.
  • Odtwarzanie rozwiązania — marsz po tabeli od celu do bazy śladem decyzji, które dały optimum.

📌 Najważniejsze w pigułce

  • Dwie linijki notesu zamieniają wykładniczego Fibonacciego w liniowego — niepowtarzanie pracy to supermoc.
  • Przepis dynamiczny: podproblem → zależność (min/max po opcjach) → tabela od dołu → odczyt (i ślad decyzji).
  • Dynamiczne ≠ zachłanne: rozważa wszystkie opcje (stąd optimum), ale każdą dokładnie raz (stąd szybkość).

🎒 Zadania

  1. Wypełnij tabelę $M$ dla monet {1, 3, 4} i kwot 0–10. Dla których kwot zachłanność (8.1) daje wynik gorszy od $M$?
Wskazówka i odpowiedź

$M$: 0,1,2,1,1,2,2,2,2,3,3 (np. $M(7)=M(3)+1=2$ — monety 3+4). Zachłanność: dla 6 daje 3 (4+1+1) vs $M(6)=2$; dla 9: 4+4+1 = 3 = $M(9)$ ✓; dla 10: 4+4+1+1 = 4 vs $M(10) = 3$ (3+3+4)! Myli się na 6 i 10 (w zakresie do 10). Tabela nie tylko liczy — certyfikuje: masz dowód optymalności dla każdej kwoty, czarno na białym.

  1. Schody mają $n$ stopni; wchodzisz krokami po 1 lub 2 stopnie. Ile jest różnych sposobów wejścia? Zdefiniuj podproblem, zależność, bazę — i policz dla $n = 10$.
Wskazówka i odpowiedź

$S(n)$ = liczba sposobów na $n$ stopni. Ostatni krok: z $n-1$ (krok 1) albo z $n-2$ (krok 2) → $S(n) = S(n-1) + S(n-2)$; baza $S(1) = 1$, $S(2) = 2$. To… Fibonacci w przebraniu! $S(10) = 89$. Połowa siły dynamicznego to rozpoznawanie znajomej zależności pod nową historyjką — schody, króliki, układanie płytek 1×2: jeden wzór, sto kostiumów. (Na maturze ta umiejętność bywa warta więcej niż kodowanie.)

  1. Wróć do plecaka z 8.2. Podproblem: $P(i, w)$ = największa wartość używając pierwszych $i$ przedmiotów przy udźwigu $w$. Zapisz zależność (dwie opcje: bierzesz przedmiot $i$ albo nie) i policz tabelę dla przedmiotów {(7 kg, 10), (4 kg, 6), (4 kg, 6)} i $W = 8$.
Wskazówka i odpowiedź

$P(i, w) = \max\big(P(i-1, w),\ P(i-1, w - w_i) + v_i\big)$ (druga opcja tylko gdy $w_i \le w$); baza $P(0, \cdot) = 0$. Tabela 3×9; kluczowe wpisy: $P(1, 7..8) = 10$; $P(2, 8) = \max(10, P(1,4)+6=6) = 10$; $P(3, 8) = \max(P(2,8)=10, P(2,4)+6 = 6+6 = 12) = \mathbf{12}$ — dwa srebra, dokładnie optimum, które zachłanność przegapiła. Koszt: $n \times W$ komórek — dla 1000 przedmiotów i udźwigu 10 000 to 10 mln operacji, ułamek sekundy tam, gdzie pełny przegląd potrzebowałby $2^{1000}$. (I obiecane zastrzeżenie z 8.2: tabela rośnie z udźwigiem — dla astronomicznego $W$ i ona kapituluje.)

🔍 Sprawdź, czy umiesz

  • Dopisać spamiętywanie do dowolnej rekurencji i wyjaśnić, co zmienia w drzewie wywołań.
  • Ułożyć podproblem + zależność + bazę dla nowej historyjki i wypełnić tabelę ręcznie.
  • Odtworzyć z tabeli nie tylko wartość optimum, ale i decyzje, które do niej prowadzą.

Ucz się tej jednostki z asystentem