गतिशील प्रोग्रामिङ कहिले लागू हुन्छ बनाम लोभी?

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 को साथ अत्यधिक-इञ्जिनीयरिङ दुवै र असुरक्षित लोभी विकल्प को साथ अन्डर-डेलिभरिङ रोक्छ।