Dinamik programlama ne zaman açgözlü algoritmaya karşı geçerlidir?

Question

Accepted Answer

Hem DP hem de açgözlü **optimal alt yapı** gerektirir. Fark: **açgözlü** ayrıca **açgözlü seçim özelliğini** de gerektirir (yerel optimum genel olarak optimaldir), **DP** ise **birden çok seçim ve çakışan alt problemler** hakkında düşünmeniz gerektiğinde gereklidir.

## Ayrım

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

## Klasik zıtlık: bozuk para değişimi

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

Açgözlü bir seçime taahhüt eder; DP tümünü keşfeder ve en iyisini saklar.

## Her biri ne zaman geçerli?

- **Açgözlü:** aralık planlama, Huffman, Dijkstra, MST — kanıtlanmış açgözlü seçim özelliği.
- **DP:** sırt çantası, düzenleme mesafesi, genel bozuk para değişimi — seçimler etkileşime girer.

## Karmaşıklık

Açgözlü genellikle O(n log n); DP daha fazla zaman/boşluk (çoğunlukla O(n·m)) doğruluk için değişim sağlar.

## Tuzaklar

Açgözlü özelliğini kanıtlamadan kullanmak **yanlış yanıtlar** verir ve küçük testleri geçer. Şüpheniz varsa DP'ye başvurun veya açgözlü olanı brute force ile karşılaştırın.

## Neden önemli

Açgözlü geçerli olduğunda seçmek muazzam zaman kaydeder; geçerli olmadığında seçmek sessiz hatalar üretir.

Hangi paradigmanın uygun olduğunu bilmek — ve bunu kanıtlayabilmek — üst düzey bir ayrımdır.

DP ile aşırı mühendisliği ve ses çıkarmayan bir açgözlü seçimle yetersiz teslimatı önler.