Kdaj se dinamično programiranje uporablja v primerjavi s pohlepnim algoritmom?

Question

Accepted Answer

Tako DP kot pohlepni algoritem potrebujeta **optimalno podstrukturno lastnost**. Razlika: **pohlepni algoritem** zahteva tudi **pohlepno-izbire lastnost** (lokalni optimum je globalno optimalen), medtem ko je **DP** potreben, ko morate razmisliti o **več izbir in prekrivajočih se podproblemih**.

## Razlika

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

## Klasična primerjava: menjava kovancev

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

Pohlepni algoritem se zaveže eni izbiri; DP raziskuje vse in ohrani najboljšo.

## Kdaj se vsaka uporablja

- **Pohlepni:** razporeditev intervalov, Huffman, Dijkstra, MST — dokazana pohlepno-izbire lastnost.
- **DP:** nahrbtnik, uredna razdalja, splošna menjava kovancev — izbire se vplivajo.

## Kompleksnost

Pohlepni je običajno O(n log n); DP zamenja več časa/prostora (pogosto O(n·m)) za pravilnost.

## Pasti

Uporaba pohlepnega brez dokaza njegove lastnosti daje **napačne odgovore**, ki prestanejo majhne teste. Če dvomite, segrajte po DP ali preverite pohlepnega proti grobi sili.

## Zakaj je to pomembno

Izbira pohlepnega, ko je veljaven, prihrani ogromno časa; izbira, ko ni, povzroči tihe napake.

Znanje, katero paradigmo izbrati — in sposobnost dokazati jo — je razlika na višji ravni.

Preprečuje tako preobremenjevanje z DP kot tudi nezadostnost z neutemeljeno pohlepno izbiro.