Wprowadzenie do programowania dynamicznego
1. Czym jest programowanie dynamiczne?
Programowanie dynamiczne (Dynamic Programming, DP) to technika rozwiązywania problemów poprzez rozbicie na mniejsze podproblemy i zapamiętywanie wyników, aby uniknąć zbędnych obliczeń.
1.1. Kluczowe właściwości:
Problem nadaje się do DP, gdy ma:
- Optymalne podstruktury – rozwiązanie problemu składa się z rozwiązań podproblemów
- Nakładające się podproblemy – te same podproblemy obliczane wielokrotnie
Przykład: Liczby Fibonacciego
fib(5) = fib(4) + fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ ... ...
fib(2) fib(1)
fib(2) obliczane 3 razy! ← Nakładające się podproblemy
2. Problem: Liczby Fibonacciego
2.1. Rekurencja naiwna (bez DP):
Złożoność: O(2^n) – katastrofalnie wolne!
2.2. Wizualizacja drzewa wywołań:
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ │ ├── fib(1) = 1
│ │ │ └── fib(0) = 0
│ │ └── fib(1) = 1
│ └── fib(2)
│ ├── fib(1) = 1
│ └── fib(0) = 0
└── fib(3)
├── fib(2)
│ ├── fib(1) = 1
│ └── fib(0) = 0
└── fib(1) = 1
fib(3) obliczane 2 razy
fib(2) obliczane 3 razy
fib(1) obliczane 5 razy
...
Marnujemy OGROMNĄ ilość obliczeń!
3. Rozwiązanie 1: Memoization (Top-Down)
Memoization = zapamiętaj wyniki w słowniku/tablicy i używaj ponownie.
3.1. Implementacja z cache:
Złożoność: - Czasowa: O(n) ✅ - Pamięciowa: O(n) – cache + stos rekurencji
3.2. Python @lru_cache decorator:
4. Rozwiązanie 2: Tabulation (Bottom-Up)
Tabulation = buduj rozwiązanie od dołu (iteracyjnie), wypełniając tablicę.
4.1. Implementacja:
4.2. Optymalizacja pamięci:
Potrzebujemy tylko dwóch ostatnich wartości!
5. Porównanie podejść
6. Klasyczny przykład: Wchodzenie po schodach
6.1. Problem:
Masz schody o n stopniach.
Możesz wejść o 1 lub 2 stopnie na raz.
Ile jest różnych sposobów dotarcia na szczyt?
Przykład: n = 3
Sposoby:
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1
Razem: 3 sposoby
6.2. Wzór rekurencyjny:
ways(n) = ways(n-1) + ways(n-2)
Dlaczego?
- Ostatni krok: 1 stopień → pozostało ways(n-1) sposobów
- Ostatni krok: 2 stopnie → pozostało ways(n-2) sposobów
6.3. Implementacja DP:
6.4. Z optymalizacją pamięci:
7. Kiedy używać programowania dynamicznego?
7.1. Sygnały, że problem wymaga DP:
✅ "Znajdź optymalny sposób..." (minimum, maximum) ✅ "Ile jest możliwości..." (counting) ✅ "Czy możliwe jest..." (decision) ✅ Problem ma podstruktury (rozbij na mniejsze) ✅ Nakładające się podproblemy (obliczane wielokrotnie)
7.2. Przykładowe problemy DP:
- Fibonacci numbers
- Climbing stairs
- Coin change (reszta)
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- Knapsack problem (plecak)
- Edit distance (Levenshtein)
- Matrix chain multiplication
- Shortest path (Bellman-Ford)
8. Kroki rozwiązywania problemu DP
Krok 1: Zdefiniuj stan
Co reprezentuje dp[i]?
Przykład (schody):
dp[i] = liczba sposobów dotarcia do stopnia i
Krok 2: Znajdź wzór rekurencyjny
Jak dp[i] zależy od poprzednich stanów?
Przykład (schody):
dp[i] = dp[i-1] + dp[i-2]
Krok 3: Określ przypadki bazowe
Jakie są najprostsze przypadki?
Przykład (schody):
dp[1] = 1
dp[2] = 2
Krok 4: Określ kolejność obliczeń
W jakiej kolejności wypełniać tablicę?
Przykład (schody):
Od dp[3] do dp[n] (od dołu do góry)
Krok 5: Zwróć wynik
Gdzie znajduje się odpowiedź?
Przykład (schody):
dp[n]
9. Memoization vs Tabulation
9.1. Porównanie:
| Aspekt | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Podejście | Rekurencyjne | Iteracyjne |
| Kierunek | Od góry (n → 0) | Od dołu (0 → n) |
| Obliczenia | Tylko potrzebne | Wszystkie |
| Stos | O(n) ❌ | O(1) ✅ |
| Prostota | ✅ Intuicyjna | Wymaga przemyślenia |
| Debugowanie | Trudniejsze | ✅ Łatwiejsze |
9.2. Kiedy używać którego?
Memoization (Top-Down): - ✅ Gdy nie wszystkie podproblemy są potrzebne - ✅ Gdy rekurencja jest naturalna - ✅ Prototypowanie (szybsze)
Tabulation (Bottom-Up): - ✅ Gdy wszystkie podproblemy są potrzebne - ✅ Gdy optymalizujesz pamięć - ✅ Produkcja (szybsza, mniej pamięci)
10. Problem: Minimalna liczba monet (Coin Change)
10.1. Problem:
Masz monety o nominałach [1, 2, 5]
Jaka jest minimalna liczba monet potrzebna do wydania reszty n?
Przykład: n = 11
Rozwiązanie: 5 + 5 + 1 = 3 monety
10.2. Wzór rekurencyjny:
dp[i] = minimalna liczba monet dla kwoty i
dp[i] = min(dp[i - coin] + 1) dla wszystkich coin ≤ i
10.3. Implementacja:
Złożoność: O(amount × len(coins))
11. Wizualizacja tablicy DP
Wynik:
Coins: [1, 2, 5], Amount: 11
Tablica DP:
dp[ 1] = 1 (1)
dp[ 2] = 1 (2)
dp[ 3] = 2 (2+1)
dp[ 4] = 2 (2+2)
dp[ 5] = 1 (5)
dp[ 6] = 2 (5+1)
dp[ 7] = 2 (5+2)
dp[ 8] = 3 (5+2+1)
dp[ 9] = 3 (5+2+2)
dp[10] = 2 (5+5)
dp[11] = 3 (5+5+1)
Wynik: 3
12. Odtwarzanie rozwiązania
12.1. Nie tylko wartość, ale też ścieżka:
13. Podsumowanie
Programowanie dynamiczne:
- Technika rozwiązywania problemów z optymalnymi podstrukturami
- Zapamiętywanie wyników – unikanie ponownych obliczeń
- Dwa podejścia: Memoization (top-down) i Tabulation (bottom-up)
Kluczowe właściwości problemu DP:
- Optymalne podstruktury – problem rozbija się na podproblemy
- Nakładające się podproblemy – obliczane wielokrotnie
Podejścia:
| Podejście | Implementacja | Kierunek | Pamięć stosu | Szybkość |
|---|---|---|---|---|
| Memoization | Rekurencja | Top-Down | O(n) ❌ | Średnia |
| Tabulation | Iteracja | Bottom-Up | O(1) ✅ | Szybsza ✅ |
Przykłady:
Kroki rozwiązywania:
- Zdefiniuj stan – co reprezentuje dp[i]?
- Wzór rekurencyjny – jak dp[i] zależy od poprzednich?
- Przypadki bazowe – najmniejsze problemy
- Kolejność obliczeń – jak wypełniać tablicę?
- Zwróć wynik – gdzie jest odpowiedź?
Złożoność:
Naiwna rekurencja: O(2^n) ❌
Memoization/Tabulation: O(n) ✅
Przykład: Fibonacci
- fib_recursive(40) → ~10 sekund
- fib_memoization(40) → 0.00001 sekundy
- 1,000,000x szybsze! ✅
Kiedy używać DP:
✅ Problem ma optymalne podstruktury ✅ Nakładające się podproblemy ✅ "Znajdź optymalny sposób..." ✅ "Ile jest możliwości..." ✅ "Czy możliwe jest..."
Typowe problemy DP:
- Fibonacci, schody (kombinacje)
- Coin change (optymalizacja)
- Knapsack (plecak)
- LCS, LIS (sekwencje)
- Edit distance (podobieństwo)
- Shortest paths (grafy)
Co dalej warto poznać:
- Memoization – szczegóły implementacji
- Tabulation – optymalizacje pamięci
- Knapsack problem – klasyczny problem DP
- LCS/LIS – problemy sekwencyjne
- Matrix chain multiplication – wielowymiarowy DP
- DP na grafach – Bellman-Ford, Floyd-Warshall