Algorytm zachłanny vs programowanie dynamiczne — kluczowa różnica?

Głębiej

Kluczowa różnica to *gwarancja optimum i dowód poprawności*.

Zachłanny:

• Wybiera lokalnie najlepszą decyzję teraz.
• Działa tylko, gdy zachodzi własność zachłannego wyboru (lokalne optimum da się rozszerzyć do globalnego).

DP:

• Definiujesz stany i przejścia.
• Opiera się o optimal substructure + overlapping subproblems.
• Daje optimum (przy poprawnym modelu), często kosztem czasu/pamięci.

Przykłady

• Greedy działa: interval scheduling (najwcześniej kończące), Huffman.
• Greedy nie działa: 0/1 knapsack, wiele systemów monet.
• DP działa: knapsack, edit distance, LIS (często z optymalizacją).

Typowe pułapki

• Użycie greedy „bo działa na przykładach” bez argumentu poprawności.
• DP ze zbyt dużym stanem (O(n^2) i więcej) bez analizy ograniczeń.