Wprowadzenie
Dynamic Programming (DP) to potężna technika algorytmiczna, która rozwiązuje problemy poprzez rozbijanie ich na mniejsze podproblemy, zapamiętywanie wyników i ponowne ich wykorzystywanie, aby uniknąć powtarzania obliczeń.
Dwa główne podejścia
- Top-Down (Memoization) – rekurencja + zapamiętywanie wyników
- Bottom-Up (Tabulation) – iteracyjne wypełnianie tabeli od najmniejszych podproblemów
Klasyczne problemy rozwiązywane DP
- Fibonacci Sequence
- Knapsack Problem (Problem Plecakowy)
- Longest Common Subsequence (LCS)
- Edit Distance (Odległość Levenshteina)
- Matrix Chain Multiplication
- 0/1 Knapsack, Coin Change, Longest Increasing Subsequence
Kiedy stosować Dynamic Programming?
Problem musi mieć dwie cechy:
- Optimal Substructure – optymalne rozwiązanie problemu można zbudować z optymalnych rozwiązań podproblemów
- Overlapping Subproblems – te same podproblemy pojawiają się wielokrotnie
Zastosowanie w AI
Dynamic Programming jest szeroko używane w:
- Algorytmach uczenia ze wzmocnieniem (Reinforcement Learning)
- Optymalizacji modeli AI
- Przetwarzaniu języka naturalnego
- Bioinformatyce i sekwencjonowaniu DNA