Kdy se dynamické programování používá oproti hladovému přístupu?

Question

Accepted Answer

DP i hladový přístup vyžadují **optimální podstrukturu**. Rozdíl: **hladový** také vyžaduje **vlastnost hladové volby** (lokální optimum je globálně optimální), zatímco **DP** je potřebný, když musíte zvážit **více možností a překrývající se dílčí problémy**.

## Rozlišení

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

## Klasický kontrast: výměna mincí

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

Hladový přístup se zavazuje jednou volbou; DP zkoumá všechny a zachovává tu nejlepší.

## Kdy se každý používá

- **Hladový:** plánování intervalů, Huffman, Dijkstra, MST — ověřená vlastnost hladové volby.
- **DP:** batoh, vzdálenost úprav, obecná výměna mincí — volby se navzájem ovlivňují.

## Složitost

Hladový přístup je obvykle O(n log n); DP vyměňuje více času/prostoru (často O(n·m)) za správnost.

## Úskalí

Verejné používání hladového přístupu bez prokázání jeho vlastnosti dává **špatné odpovědi**, které projdou malými testy. Pokud si nejste jistí, použijte DP nebo ověřte hladový přístup hrubou silou.

## Proč to záleží

Volba hladového přístupu, když je platný, ušetří obrovský čas; volba, když není, vede k tichým chybám.

Vědět, který paradigma vyhovuje — a být schopen jej prokázat — je rozlišení na úrovni senior.

Prevenci před přeingenerováním pomocí DP a nedostatečným dodáním s nesprávnou hladovou volbou.