Когда применяется динамическое программирование в сравнении с жадным алгоритмом?

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 или проверяйте жадный алгоритм против перебора.

## Почему это важно

Выбор жадного алгоритма, когда он верен, экономит огромное количество времени; выбор его, когда он неправ, создает скрытые ошибки.

Знание того, какая парадигма подходит — и возможность это доказать — это отличие уровня senior.

Оно предотвращает как избыточное усложнение с помощью DP, так и недостаточное выполнение с помощью необоснованного жадного выбора.