När gäller dynamisk programmering kontra girig algoritm?

Question

IT Interview Practice · Accepted Answer

Både DP och girig behöver **optimal substruktur**. Skillnaden: **girig** kräver också den **giriga-val-egenskapen** (ett lokalt optimum är globalt optimalt), medan **DP** behövs när du måste överväga **flera val och överlappande delproblem**.

## Distinktionen

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

## Klassisk kontrast: myntväxling

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

Girig förbinder sig till ett val; DP utforskar alla och behåller det bästa.

## När varje gäller

- **Girig:** intervallplanering, Huffman, Dijkstra, MST — bevisad girig-val-egenskap.
- **DP:** knapsack, redigeringsdistans, allmän myntväxling — val interagerar.

## Komplexitet

Girig är vanligtvis O(n log n); DP byter mer tid/utrymme (ofta O(n·m)) för korrekthet.

## Fallgropar

Att använda girig utan att bevisa dess egenskap ger **felaktiga svar** som klarar små tester. Om du är osäker, gripa tag i DP eller verifiera girig mot brute force.

## Varför det är viktigt

Att välja girig när det är giltigt sparar enorm tid; att välja det när det inte är det producerar tysta buggar.

Att veta vilken paradigm som passar — och kunna bevisa den — är en skiljande faktor på högre nivå.

Det förhindrar både överingenjörering med DP och underlevering med ett osäkert girig val.

Distinktionen

Klassisk kontrast: myntväxling

När varje gäller

Komplexitet

Fallgropar

Varför det är viktigt

Relaterade frågor