Padrão 3: Knapsack (coin change)
"Compor um alvo combinando itens" é uma das famílias mais comuns de DP — a família mochila (knapsack). O Coin Change é o representante perfeito: formar um valor com o menor número de moedas.
Tente primeiro: Coin Change
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dadas moedas de valores coins (quantidade ilimitada de cada) e um amount, retorne o menor número de moedas que soma exatamente amount, ou -1 se for impossível.
Exemplo: coins = [1,2,5], amount = 11 → 3 (5+5+1).
Tentou? Um guloso ("pegue sempre a maior moeda que cabe") falha em alguns casos (ex.: moedas [1,3,4] para 6: guloso dá 4+1+1=3, mas 3+3=2 é melhor). A teoria abaixo mostra por que aqui é preciso DP.
A teoria: a tabela do valor-alvo
Defina dp[a] = menor número de moedas para formar o valor a. Para
calcular dp[a], tente usar cada moeda m como a última: se você usa m,
o resto é a - m, que já foi resolvido. Pegue o melhor entre as opções:
dp[a] = min sobre cada moeda m (com m <= a) de: dp[a - m] + 1
casos-base: dp[0] = 0 (zero moedas para formar zero)
inicialize o resto com "infinito" (impossível)
Como cada moeda pode ser usada quantas vezes quiser, isto é o knapsack
ilimitado (unbounded). Preencha dp de 1 até amount; veja a tabela se
formando, com o cursor a consultando dp[a - m]:
No fim, dp[amount] é a resposta — ou -1 se ficou "infinito" (impossível
formar o valor).
Por que é O(amount × moedas)?
São amount + 1 estados (dp[0..amount]), e cada um testa todas as moedas
→ tempo O(amount × nº de moedas), espaço O(amount). É o "estados × custo
por estado" da aula 1 em ação: amount estados × O(moedas) cada.
Por que o guloso falha aqui (e na aula passada o Jump Game não)
No Jump Game, a escolha local ("ir o mais longe") garantia o ótimo. No Coin Change, pegar a maior moeda não garante: às vezes uma combinação de moedas menores usa menos peças. Como a escolha local pode levar a um beco, é preciso considerar todas as opções e reusar subproblemas — exatamente o que a DP faz. Reconhecer essa diferença é meio caminho.
Variações da família knapsack
| Problema | Estado | Recorrência |
|---|---|---|
| Coin Change (mín. moedas) | dp[a] = mín. moedas p/ a | min(dp[a-m]+1) |
| Combination Sum IV (contar) | dp[a] = nº de combinações p/ a | soma de dp[a-m] |
| Partition Equal Subset | dp[v] = dá p/ formar v? | dp[v] ou dp[v-num] (0/1) |
Repare: Coin Change e Combination Sum IV são quase iguais — só trocam
min(...)+1 por soma(...), porque um conta o mínimo de moedas e o outro
quantas combinações. Já o Partition é knapsack 0/1 (cada item usado
no máximo uma vez), o que muda a direção do laço. Mesmo esqueleto, perguntas
diferentes.
🧠 Quiz de fixação
0/41. No Coin Change, o que dp[a] representa e qual a recorrência?
2. Por que o Coin Change é um knapsack 'ilimitado' (unbounded)?
3. Por que um guloso ('pegue a maior moeda que cabe') falha no Coin Change?
4. Coin Change (mín. moedas) e Combination Sum IV (contar combinações) diferem em quê?
Resumo
- Knapsack: compor um alvo a partir de itens;
dp[a]indexado pelo valor. - Coin Change:
dp[a] = min(dp[a-m] + 1)sobre as moedas (unbounded: moedas reutilizáveis). - O(amount × moedas) — estados × custo por estado.
- Guloso falha (a escolha local engana) ⇒ DP. Combination Sum IV é o mesmo molde, contando combinações.
Próxima aula: a tabela ganha duas dimensões — DP em grid.