Πότε ισχύει ο δυναμικός προγραμματισμός έναντι της άπληστης μεθόδου;

Question

Accepted Answer

Τόσο ο DP όσο και η άπληστη μέθοδος χρειάζονται **βέλτιστη υποδομή**. Η διαφορά: η **άπληστη** απαιτεί επίσης την **ιδιότητα άπληστης επιλογής** (ένα τοπικό βέλτιστο είναι παγκοσμίως βέλτιστο), ενώ ο **DP** είναι απαραίτητος όταν πρέπει να λάβετε υπόψη **πολλαπλές επιλογές και επικαλυπτόμενα υποπροβλήματα**.

## Η διάκριση

```text
Optimal substructure?  -- both need this
  + greedy-choice property holds?  -> GREEDY (fast, one pass of choices)
  + must compare many sub-solutions / they overlap?  -> DYNAMIC PROGRAMMING
```

## Κλασική αντίθεση: ανταλλαγή νομισμάτων

```python
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)  # try every coin
    return dp[amount]

min_coins(6, [1, 3, 4])               # -> 2
```

Η άπληστη μέθοδος δεσμεύεται σε μία επιλογή· ο DP εξερευνά όλες και κρατά την καλύτερη.

## Πότε ισχύει το καθένα

- **Άπληστη:** χρονοπρόγραμμα διαστημάτων, Huffman, Dijkstra, MST — αποδεδειγμένη ιδιότητα άπληστης επιλογής.
- **DP:** σακίδιο, απόσταση επεξεργασίας, γενική ανταλλαγή νομισμάτων — οι επιλογές αλληλεπιδρούν.

## Πολυπλοκότητα

Η άπληστη μέθοδος είναι συνήθως O(n log n)· ο DP ανταλλάσσει περισσότερο χρόνο/χώρο (συχνά O(n·m)) για ορθότητα.

## Παγίδες

Η χρήση της άπληστης μεθόδου χωρίς απόδειξη της ιδιότητάς της δίνει **λανθασμένες απαντήσεις** που περνούν μικρές δοκιμές. Όταν έχετε αμφιβολία, χρησιμοποιήστε DP ή επαληθεύστε την άπληστη μέθοδο έναντι της ωμής δύναμης.

## Γιατί έχει σημασία

Η επιλογή της άπληστης μεθόδου όταν είναι έγκυρη εξοικονομεί τεράστιο χρόνο· η επιλογή της όταν δεν είναι δημιουργεί σιωπηλά σφάλματα.

Η γνώση ποιο παράδειγμα ταιριάζει — και η ικανότητα να το αποδείξει — είναι διάκριση σε επίπεδο senior.

Προλαμβάνει τόσο την υπερ-μηχανική με DP όσο και την υποδιανομή με μια ασφαλή άπληστη επιλογή.