โปรแกรมมิ่งแบบไดนามิกใช้เมื่อใด เมื่อเทียบกับอัลกอริทึมแบบโลภ?

Question

Accepted Answer

DP และโลภทั้งคู่ต้องการ **โครงสร้างย่อยที่เหมาะสม** ความแตกต่าง: **โลภ** ยังต้องการ **คุณสมบัติการเลือกแบบโลภ** (ความเหมาะสมของท้องถิ่นเป็นความเหมาะสมทั่วโลก) ในขณะที่ **DP** จำเป็นเมื่อคุณต้องพิจารณา **ตัวเลือกหลายรายการและปัญหาย่อยที่ทับซ้อน**

## ความแตกต่าง

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

## การเปรียบเทียบแบบคลาสสิก: การเปลี่ยนเหรียญ

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

โลภมุ่งมั่นกับตัวเลือกเดียว DP สำรวจทั้งหมดและเก็บรักษาสิ่งที่ดีที่สุด

## เมื่อแต่ละคนใช้ได้

- **โลภ:** การกำหนดตารางเวลาช่วงเวลา Huffman Dijkstra MST — คุณสมบัติการเลือกแบบโลภที่พิสูจน์แล้ว
- **DP:** knapsack ระยะห่างการแก้ไข การเปลี่ยนเหรียญทั่วไป — ตัวเลือกที่โต้ตอบกัน

## ความซับซ้อน

โลภมักเป็น O(n log n) DP แลกเวลา/พื้นที่เพิ่มเติม (มักเป็น O(n·m)) เพื่อความถูกต้อง

## ข้อขัดของ

การใช้โลภโดยไม่พิสูจน์คุณสมบัติของมันให้ **คำตอบที่ผิด** ที่ผ่านการทดสอบขนาดเล็ก เมื่อมีข้อสงสัย ให้ไปที่ DP หรือตรวจสอบโลภกับความแข็งแกร่งเดรัจฉาน

## ทำไมนี่จึงสำคัญ

การเลือกโลภเมื่อใช้ได้จะช่วยประหยัดเวลาอย่างมหาศาล การเลือกเมื่อไม่ได้ผลจะสร้างข้อบกพร่องแบบเงียบ

การรู้ว่าอัลกอริทึมไหนเหมาะสม — และสามารถพิสูจน์ได้ — เป็นความแตกต่างในระดับอาวุโส

มันป้องกันการใช้วิศวกรรมเกิน DP และการให้บริการไม่เพียงพอด้วยตัวเลือกโลภที่ไม่มีเสียง