Quando a programação dinâmica se aplica versus guloso?

Question

Accepted Answer

Tanto DP quanto guloso precisam de **subestrutura ótima**. A diferença: **guloso** também requer a **propriedade da escolha gulosa** (um ótimo local é globalmente ótimo), enquanto **DP** é necessário quando você deve considerar **múltiplas escolhas e subproblemas sobrepostos**.

## A distinção

```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
```

## Contraste clássico: troco em moedas

```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
```

Guloso se compromete com uma escolha; DP explora todas e mantém a melhor.

## Quando cada um se aplica

- **Guloso:** agendamento de intervalos, Huffman, Dijkstra, MST — propriedade da escolha gulosa comprovada.
- **DP:** mochila, distância de edição, troco em moedas geral — as escolhas interagem.

## Complexidade

Guloso é geralmente O(n log n); DP troca mais tempo/espaço (frequentemente O(n·m)) por correção.

## Armadilhas

Usar guloso sem provar sua propriedade dá **respostas erradas** que passam em testes pequenos. Na dúvida, recorra a DP ou verifique guloso contra força bruta.

## Por que isso importa

Escolher guloso quando é válido economiza tempo enorme; escolhê-lo quando não é produz bugs silenciosos.

Saber qual paradigma se encaixa — e ser capaz de prová-lo — é uma distinção de nível sênior.

Evita tanto o sobre-engenharia com DP quanto o entregável deficiente com uma escolha gulosa infundada.