Kiedy zastosować programowanie dynamiczne a kiedy podejście chciwe?

Question

Accepted Answer

Zarówno DP jak i podejście chciwe wymagają **optymalnej podstruktury**. Różnica: podejście **chciwe** dodatkowo wymaga **własności wyboru chciwego** (optimum lokalne jest optimum globalnym), natomiast **DP** jest potrzebne, gdy trzeba rozważyć **wiele wyborów i nakładające się podproblemy**.

## Rozróżnienie

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

## Klasyczne porównanie: wydawanie reszty

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

Podejście chciwe zatwierdza jeden wybór; DP bada wszystkie i wybiera najlepszy.

## Kiedy zastosować każde

- **Chciwe:** planowanie przedziałów czasowych, algorytm Huffmana, Dijkstra, MST — udowodniona własność wyboru chciwego.
- **DP:** problem plecakowy, edycja odległości, ogólne wydawanie reszty — wybory się przenikają.

## Złożoność

Podejście chciwe to zwykle O(n log n); DP wymienia więcej czasu/pamięci (często O(n·m)) na poprawność.

## Pułapki

Zastosowanie podejścia chciwego bez udowodnienia jego własności daje **błędne odpowiedzi**, które przechodzą małe testy. Gdy są wątpliwości, sięgnij po DP lub zweryfikuj podejście chciwe wobec rozwiązania brute force.

## Dlaczego to ważne

Wybór podejścia chciwego, gdy jest ono prawidłowe, oszczędza ogromnie czasu; wybór go, gdy nie jest, powoduje subtelne błędy.

Umiejętność określenia, który paradygmat pasuje — i możliwość jego udowodnienia — to rozróżnienie na poziomie seniora.

Zapobiega to zarówno nadmiarowej inżynierii z DP, jak i niedostarczeniu wartości z niezasadnym wyborem chciwym.