Milloin dynaaminen ohjelmointi pätee verrattuna ahneeseen algoritmiin?

Question

Accepted Answer

Sekä DP että ahne algoritmi tarvitsevat **optimaalisen alistruktuurin**. Ero: **ahne** vaatii myös **ahneuden valinnan ominaisuuden** (paikallinen optimi on globaalisti optimaalinen), kun taas **DP** on välttämätön, kun sinun on pohdittava **useita valintoja ja päällekkäisiä aliongelmia**.

## Erottelu

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

## Klassinen kontrasti: kolikonvaihto

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

Ahne sitoutuu yhteen valintaan; DP tutkii kaikkia ja säilyttää parhaan.

## Milloin kukin pätee

- **Ahne:** aikavälin ajoitus, Huffman, Dijkstra, MST — todistettu ahneuden valinnan ominaisuus.
- **DP:** reppu, muokkausmatka, yleinen kolikonvaihto — valinnat vuorovaikuttavat.

## Monimutkaisuus

Ahne on yleensä O(n log n); DP vaihtaa enemmän aikaa/tilaa (usein O(n·m)) oikeellisuuden vuoksi.

## Sudenkuopat

Ahteen käyttö ilman sen ominaisuuden todistamista antaa **väärät vastaukset**, jotka läpäisevät pienet testit. Epävarmuuden tapauksessa käytä DP:tä tai tarkista ahne raa'assa voimassa.

## Miksi sillä on merkitystä

Ahneuden valitseminen, kun se on pätevä, säästää valtavan paljon aikaa; sen valitseminen, kun se ei ole, tuottaa hiljaisia virheitä.

Tiedon siitä, mikä paradigma sopii — ja kyky todistaa se — on seniorin tason ero.

Se estää sekä DP:n yliteknisöinnin että riittämättömän toimittamisen epäturvallisella ahneella valinnalla.