Kada taikoma dinaminė programa versus greedy algoritmas?

Question

Accepted Answer

Tiek DP, tiek greedy reikalinga **optimalios substruktūros**. Skirtumas: **greedy** taip pat reikalinga **greedy-choice savybė** (lokalus optimumas yra globaliai optimalus), o **DP** reikalinga, kai turite atsižvelgti į **kelis sprendimus ir persidengančias subproblemas**.

## Skirtumas

```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
```

## Klasikinis kontrastas: monetos keitimas

```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
```

Greedy įsipareigoja vienam sprendimui; DP tyrinėja visus ir saugo geriausią.

## Kada kiekvienas taikomas

- **Greedy:** intervalų planavimas, Huffman, Dijkstra, MST — įrodyta greedy-choice savybė.
- **DP:** kuprinė, redagavimo distancija, bendras monetos keitimas — sprendimai sąveikauja.

## Sudėtingumas

Greedy paprastai yra O(n log n); DP keičia daugiau laiko/atminties (dažnai O(n·m)) už teisingumą.

## Pavojus

Greedy naudojimas neįrodant jos savybės duoda **neteisingus atsakymus**, kurie praeina mažus testus. Kai dvejojate, siekite DP arba patikrinkite greedy pagal brute force.

## Kodėl tai svarbu

Greedy pasirinkimas, kai jis teisingas, taupa didžiulius laikus; pasirinkimas, kai jis neteisingas, sukuria tylias klaidas.

Žinojimas, kuris paradigma tinka — ir galėjimas tai įrodyti — yra aukštesnio lygio skirtumas.

Tai nuo abiejų pusių prevencinė priemonė: nuo per daug inžinerijos su DP ir nuo nepakankamo greedy pasirinkimo, kuris negrindžiamas.