Când se aplică programarea dinamică versus greedy?

Question

Accepted Answer

Atât DP cât și greedy necesită **structură optimală de subprobleme**. Diferența: **greedy** necesită, de asemenea, **proprietatea alegerii greedy** (un optim local este optim global), în timp ce **DP** este necesar atunci când trebuie să iei în considerare **multiple alegeri și subprobleme suprapuse**.

## Distincția

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

## Contrast clasic: schimb monede

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

Greedy se angajează la o alegere; DP explorează pe toate și păstrează pe cea mai bună.

## Când se aplică fiecare

- **Greedy:** planificarea intervalelor, Huffman, Dijkstra, MST — proprietatea alegerii greedy dovedită.
- **DP:** rucsac, distanța de editare, schimb de monede general — alegerile interacționează.

## Complexitate

Greedy este de obicei O(n log n); DP schimbă mai mult timp/spațiu (adesea O(n·m)) pentru corectitudine.

## Capcane

Folosirea greedy fără a-i dovedi proprietatea dă **răspunsuri greșite** care trec teste mici. Când nu ești sigur, apelează la DP sau verifică greedy împotriva forței brute.

## De ce contează

Alegerea greedy atunci când este validă economisește timp imens; alegerea ei atunci când nu este produce bug-uri silențioase.

Cunoașterea paradigmei care se potrivește — și capacitatea de a o dovedi — este o distincție de nivel senior.

Previne atât supra-ingineria cu DP cât și sub-livrarea cu o alegere greedy nevalidă.