Når gjelder dynamisk programmering versus grådige algoritmer?

Question

Accepted Answer

Både DP og grådige algoritmer trenger **optimal substruktur**. Forskjellen: **grådige algoritmer** krever også **den grådige valg-egenskapen** (et lokalt optimum er globalt optimalt), mens **DP** er nødvendig når du må vurdere **flere valg og overlappende delproblemer**.

## Skillet

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

```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ådige algoritmer forplikter seg til ett valg; DP utforsker alle og beholder det beste.

## Når hver gjelder

- **Grådige algoritmer:** intervallplanlegging, Huffman, Dijkstra, MST — bevist grå valg-egenskapen.
- **DP:** ryggsekk, redigeringsdistanse, generell myntbytting — valg påvirker hverandre.

## Kompleksitet

Grådige algoritmer er vanligvis O(n log n); DP handler mer tid/plass (ofte O(n·m)) for korrekthet.

## Fallgruver

Å bruke grådige algoritmer uten å bevise egenskapen gir **feil svar** som består små tester. Når du er i tvil, velg DP eller verifiser grådige algoritmer mot brute force.

## Hvorfor det betyr noe

Å velge grådige algoritmer når det er gyldig sparer enorm tid; å velge det når det ikke er, produserer stille feil.

Å vite hvilken paradigme som passer — og å kunne bevise det — er en skillelinje på seniornivå.

Det forhindrer både overteoretisering med DP og underlevering med et usunt grådigt valg.