Kur zbatohet programimi dinamik kundrejt zgjedhjes grisy?

Question

Accepted Answer

Të dyja DP dhe greedy kanë nevojë për **strukturën optimale të nënproblemit**. Dallimi: **greedy** kërkon gjithashtu **pronësinë e zgjedhjes greedy** (një optimum lokal është globalisht optimal), ndërsa **DP** nevojitet kur duhet të merrni në konsideratë **shumë zgjedhje dhe nënprobleme që mbivendosen**.

## Dallimi

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

## Kontrasti klasik: ndryshim monedhash

```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 e angazhon veten për një zgjedhje; DP eksploron të gjitha dhe mban më të mirën.

## Kur zbatohet secila

- **Greedy:** planifikimi i intervaleve, Huffman, Dijkstra, MST — vëtëm pronësinë e zgjedhjes greedy.
- **DP:** çanta, distanca redaksioni, ndryshim i përgjithshëm monedhash — zgjedhjet ndërveprojnë.

## Kompleksiteti

Greedy është zakonisht O(n log n); DP ndryshohet më shumë kohë/hapësirë (shpesh O(n·m)) për korrektësinë.

## Grackjet

Përdorimi i greedy pa vërësuar pronësinë e tij jep **përgjigje të gabuara** që kalojnë testet e vogla. Nëse dyshoni, rrini në DP ose verifikoni greedy kundër forcës brutale.

## Pse është e rëndësishme

Zgjedhja e greedy kur është e vlefshme kursen kohë të madhe; zgjedhja e tij kur nuk është prodhon gabime të heshta.

Dija se cila paradigmë përshtatet — dhe përfundim të vërtetosh — është një dallim në nivel të lartë.

Është parandalon të dyja mbiprojektimin me DP dhe nëndeliverimin me një zgjedhje greedy të padëgjuar.