డైనమిక్ ప్రోగ్రామింగ్ లోభ సంబంధం ఎప్పుడు వర్తిస్తుంది?

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 అందరిని అన్వేషిస్తుంది మరియు ఉత్తమాన్ని ఉంచుకుంటుంది.

## ప్రతిదీ ఎప్పుడు వర్తిస్తుంది

- **లోభం:** విరామ సమయూచన, హఫ్‌మాన్, డిజ్‌ట్రా, MST — రుజువు చేసిన లోభ-ఎంపిక సంపత్తి.
- **DP:** నేపధ్యం, సవరణ దూరం, సాధారణ నాణెం మార్పు — ఎంపికలు సంకర్షణ.

## సంక్లిష్టత

లోభం సాధారణంగా O(n log n); DP నిఖిల సమయం/స్థలం (తరచుగా O(n·m)) ఖచ్చితత్వం కోసం.

## చిక్కులు

లోభాన్ని దాని సంపత్తిని రుజువు చేయకుండా ఉపయోగించడం **చెడ్డ సమాధానాలు** చిన్న పరీక్ష ఆందోళన కిటకిలను ఇస్తుంది. సందేహం ఉంటే, DP కోసం చేరుకోండి లేదా లోభాన్ని బ్రూట్ ఫోర్స్ నుండి వేరుచేయండి.

## ఇది ఎందుకు ముఖ్యమైనది

లోభాన్ని చెల్లుబాటు అయినప్పుడు ఎంచుకోవడం భారీ సమయాన్ని సేవ్ చేస్తుంది; అది చెల్లుబాటు కానప్పుడు ఎంచుకోవడం నిశ్చిన్న బగ్‌లను ఉత్పత్తి చేస్తుంది.

ఏ నమూనా సరిపోతుందో తెలుసుకోవడం — మరియు దానిని నిరూపించగల సామర్థ్యం — సీనియర్-స్థర వైవిధ్యం.

ఇది DP తో ఎక్కువ ఇంజనీరింగ్ మరియు నిశ్చయత లేని లోభ ఎంపిక తో కనిపించకుండా ఉంచుతుంది.