8 min
← Voltar
1
0 XP

Coin Change

Dado um conjunto de moedas e um valor alvo, encontre o número mínimo de moedas necessárias para somar o valor. Clássico problema de DP bottom-up.

MédiaO(n × m) / O(n)DPBottom-upOtimizaçãoCombinatória

Visualizador Interativo

Pensamento DP

Como pensar em Coin Change como DP

etapa 1 / 5
◇

Identificar Estado

Pergunta-guia“Qual a menor unidade de problema que, se eu souber resolver, me ajuda a resolver o todo?”

Aqui o "problema" é formar um valor exato com moedas. A menor unidade é formar cada valor menor que o alvo. Se eu souber a resposta para todos os valores menores, posso derivar a do alvo.

Defino então um estado indexado pelo valor: para cada j de 0 até amount, quanto custa formar j?

dp[j] = mínimo de moedas para formar o valor j
Vira em códigopython
1def coin_change(coins, amount):
2 INF = float('inf')
3dp = [INF] * (amount + 1)
4 dp[0] = 0
5 choice = [None] * (amount + 1)
Moedas
1
3
4
Alvo
6
Passo1 / 29
Tabela dp[j]
0
0
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
dp[0] = 0, dp[1..6] = ∞ — preencheremos cada célula olhando para células menores já resolvidas.
Combinação acumulada
aguardando backtrack…
Velocidade:1100ms
Historico de Passos
#0Inicializando dp[0]=0 e dp[1..6]=∞. Vamos preencher de baixo pra cima.

Como Funciona

Coin Change é o exemplo canônico de Programação Dinâmica bottom-up. A ideia central: para resolver o valor j, basta saber a resposta dos valores menores. Se dp[j] = mínimo de moedas para formar j, então para cada moeda c disponível, uma forma de chegar em j é usar c como última moeda, vindo de j - c. Logo: dp[j] = min(dp[j - c] + 1) para toda moeda c ≤ j Resolvemos dp[0], dp[1], ..., dp[amount] em ordem crescente. Quando chegamos em dp[amount], já temos a resposta. Cada subproblema é resolvido uma única vez e reutilizado — daí o ganho sobre a recursão pura. Para reconstruir a combinação de moedas (não só o tamanho), guardamos em choice[j] qual moeda foi usada para atingir dp[j], e fazemos backtrack a partir de amount.

“A estrutura "subproblemas sobrepostos" é o que diferencia DP de divide-and-conquer. Mesmos subvalores são usados várias vezes — memoizá-los transforma uma recursão exponencial em algoritmo polinomial.”

Passo a Passo

  1. Inicializa dp[0] = 0 e dp[1..n] = infinito
  2. Para cada valor j de 1 até amount
  3. Para cada moeda c disponível
  4. Se c ≤ j, calcula candidato = dp[j-c] + 1
  5. Atualiza dp[j] se o candidato é melhor
  6. Faz backtrack a partir de dp[amount] para reconstruir as moedas

Análise de Complexidade

⏱️Tempo
O(n × m)

n = valor alvo, m = número de moedas. Cada par (j, c) é processado uma vez.

Ver prova

Total de operações: amount × |coins| = n × m

💾Espaco
O(n)

Array dp de tamanho amount + 1. Se reconstruirmos a combinação, mais um array choice de mesmo tamanho.

🎯Melhor Caso
O(n × m)

DP bottom-up sempre preenche toda a tabela — não há atalho.

⚠️Pior Caso
O(n × m)

Mesma complexidade em qualquer entrada.

Comparação com Outros Algoritmos

AlgoritmoTempoEspacoMelhor Para
Coin Change (DP)(atual)O(n × m)O(n)Encontrar o mínimo garantido
Coin Change (Recursão Pura)O(m^n)O(n)Didático — mostra a explosão exponencial sem DP
Coin Change (Guloso)O(n log n)O(1)Só funciona para certos sistemas de moedas (como o brasileiro/euro)

Dicas e Erros Comuns

  • Inicializar dp[0] com infinito (deve ser 0 — zero moedas para formar zero)
  • Iterar moedas no loop externo e valores no interno (funciona, mas confunde com o problema de combinações distintas)
  • Esquecer de checar se dp[j-c] é alcançável antes de somar 1
  • Confundir com a versão "número de formas" (que conta combinações ao invés do mínimo)

Perguntas de Entrevista

Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.

Implementacao

python
1def coin_change(coins, amount):Definição
2    INF = float('inf')
3    dp = [INF] * (amount + 1)Inicialização do DP
4    dp[0] = 0
5    choice = [None] * (amount + 1)
6 
7    for j in range(1, amount + 1):Loop de Valores
8        for c in coins:Loop de Moedas
9            if c <= j and dp[j - c] != INF:Validade
10                candidate = dp[j - c] + 1Recorrência
11                if candidate < dp[j]:
12                    dp[j] = candidate
13                    choice[j] = c
14 
15    if dp[amount] == INF:Resultado
16        return -1, []
17 
18    # Backtrack para reconstruir as moedas
19    coins_used = []
20    j = amount
21    while j > 0:
22        coins_used.append(choice[j])
23        j -= choice[j]
24 
25    return dp[amount], coins_used
26