Dynamic Programming (Programowanie Dynamiczne)

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

Powiązane pojęcia

Memoization • Tabulation • Recursion • Greedy Algorithm • Fibonacci • Knapsack • Bellman Equation • Reinforcement Learning