डायनामिक प्रोग्रामिंग कधी लागू होते विरुद्ध लोभी?

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 साठी पोहोचा किंवा लोभी ला ब्रूट फोर्सच्या विरुद्ध सत्यापित करा.

## महत्व

लोभी निवडणे जेव्हा ते वैध असते तेव्हा मोठ्या वेळेचा बचाव करते; जेव्हा ते नसते तेव्हा निवडणे गोपन बग तयार करते.

कोणती प्रतिमान बसते हे जाणून घेणे — आणि ते सिद्ध करण्यास सक्षम असणे — ही वरिष्ठ-स्तरीय भिन्नता आहे.

ते DP सह अतिरिक्त-अभियांत्रिकी आणि असंभाव्य लोभी निवडीसह अपुरे-वितरण दोन्ही प्रतिबंधित करते.