Hvornår gælder dynamisk programmering kontra grådig?

Question

Accepted Answer

Både DP og grådig har brug for **optimal understruktur**. Forskellen: **grådig** kræver også **greedy-choice property** (et lokalt optimum er globalt optimalt), mens **DP** er nødvendig, når du skal overveje **flere valg og overlappende delproblemer**.

## Sondringen

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

## Klassisk kontrast: møntskift

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

Grådig forpligter sig til ét valg; DP udforsker alle og beholder den bedste.

## Når hver gælder

- **Grådig:** intervalplanlægning, Huffman, Dijkstra, MST — bevist greedy-choice property.
- **DP:** rygsæk, redigeringsdistance, generelt møntskift — valg interagerer.

## Kompleksitet

Grådig er normalt O(n log n); DP bytter mere tid/plads (ofte O(n·m)) for korrekthed.

## Faldgruber

Brug af grådig uden at bevise dets egenskab giver **forkerte svar**, der passerer små tests. I tvivlstillfælde, brug DP eller verificer grådig mod brute force.

## Hvorfor det betyder noget

At vælge grådig, når det er gyldigt, sparer enormt tid; at vælge det, når det ikke er, producerer stille fejl.

At vide, hvilket paradigme der passer — og at kunne bevise det — er en senior-level forskel.

Det forhindrer både over-engineering med DP og under-delivering med et usundt grådigt valg.