متحرک پروگرامنگ کب لاگو ہوتی ہے بمقابلہ لالچی الگورتھم کے؟

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، edit distance، عام سکے کی تبدیلی — انتخابات آپس میں منسلک ہوتے ہیں۔

## پیچیدگی

لالچی عام طور پر O(n log n) ہے؛ DP زیادہ وقت/میموری (اکثر O(n·m)) کے ساتھ درستگی کو ترجیح دیتا ہے۔

## خطرات

لالچی کو بغیر اس کی خصوصیت ثابت کیے استعمال کرنا **غلط جوابات** دیتا ہے جو چھوٹے ٹیسٹوں میں پاس ہو جاتے ہیں۔ جب شک ہو تو DP کا سہارا لیں یا لالچی کو brute force کے خلاف تصدیق کریں۔

## یہ اہم کیوں ہے

لالچی کو منتخب کرنا جب یہ درست ہو بہت زیادہ وقت بچاتا ہے؛ اسے منتخب کرنا جب یہ غلط ہو خاموش خرابیاں پیدا کرتا ہے۔

یہ جاننا کہ کون سا نقطہ نظر موزوں ہے — اور اسے ثابت کر سکنے میں — ایک بزرگ سطح کی تمیز ہے۔

یہ DP کے ساتھ زیادہ انجینئری کرنے اور غیر معتبر لالچی انتخاب سے کم فراہمی دونوں سے بچاتا ہے۔