متى ينطبق البرمجة الديناميكية مقابل الجشع؟

Question

Accepted Answer

كل من البرمجة الديناميكية والجشع يحتاجان إلى **البنية الثنائية المثلى**. الفرق: **الجشع** يتطلب أيضًا **خاصية الاختيار الجشع** (الحد الأمثل المحلي هو الحد الأمثل عام)، بينما **البرمجة الديناميكية** ضرورية عندما يجب عليك التفكير في **اختيارات متعددة وتداخل المشاكل الفرعية**.

## التمييز

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

الجشع يلتزم باختيار واحد؛ البرمجة الديناميكية تستكشف الجميع وتبقي على الأفضل.

## متى ينطبق كل منهما

- **الجشع:** جدولة الفترات الزمنية، Huffman، Dijkstra، MST — خاصية الاختيار الجشع المثبتة.
- **البرمجة الديناميكية:** حقيبة الظهر، مسافة التحرير، صرف العملات العام — الاختيارات تتفاعل.

## التعقيد

الجشع عادة O(n log n)؛ البرمجة الديناميكية تبادل المزيد من الوقت/المساحة (عادة O(n·m)) للحصول على الصحة.

## الأخطاء الشائعة

استخدام الجشع دون إثبات خاصيته يعطي **إجابات خاطئة** تمر على الاختبارات الصغيرة. عند الشك، استخدم البرمجة الديناميكية أو تحقق من الجشع مقابل القوة الغاشمة.

## لماذا يهم

اختيار الجشع عندما يكون صحيحًا يوفر وقتًا هائلاً؛ اختياره عندما لا يكون كذلك ينتج أخطاءً صامتة.

معرفة أي نموذج يناسب — والقدرة على إثباته — هو تمييز على مستوى أعلى.

يمنع الإفراط في الهندسة باستخدام البرمجة الديناميكية والتقليل من الخيار الجشع غير الصحيح.