--- title: "Coin Change em Zig: Problema do Troco com Programação Dinâmica" url: "https://ziglang.com.br/algoritmos/coin-change-troco/" markdown_url: "https://ziglang.com.br/algoritmos/coin-change-troco.MD" description: "Resolva Coin Change em Zig: mínimo de moedas, número de combinações, reconstrução da resposta, testes e complexidade O(n × valor)." date: "2026-02-21" author: "Zig Brasil" --- # Coin Change em Zig: Problema do Troco com Programação Dinâmica Resolva Coin Change em Zig: mínimo de moedas, número de combinações, reconstrução da resposta, testes e complexidade O(n × valor). # Coin Change em Zig: Problema do Troco com Programação Dinâmica O **Coin Change**, conhecido em português como **problema do troco**, consiste em formar um valor usando um conjunto de moedas. Há duas perguntas clássicas: qual é o **menor número de moedas** necessário e quantas **combinações diferentes** conseguem formar o valor? Em Zig, ambas podem ser resolvidas com programação dinâmica em **O(n × V)**, onde `n` é a quantidade de tipos de moeda e `V` é o valor alvo. A resposta direta é: use um array `dp` com uma posição para cada valor de `0` até `V`. Em vez de testar todas as sequências de moedas, reutilize as respostas dos valores menores. Essa técnica transforma uma busca exponencial em um algoritmo previsível, com memória **O(V)**. ## As duas variantes de Coin Change Embora compartilhem a mesma ideia, as variantes guardam informações diferentes em `dp`. | Variante | Significado de `dp[v]` | Resposta para moedas `[1, 5, 10, 25]` e valor `30` | |---|---|---| | Mínimo de moedas | menor quantidade para formar `v` | 2 moedas: `25 + 5` | | Número de combinações | quantas combinações formam `v` | depende do conjunto e do valor analisado | Na variante de mínimo, inicializamos `dp[0] = 0` e as demais posições com um valor que representa “infinito”. Para cada valor, tentamos terminar a solução com cada moeda disponível: ```text dp[0] = 0 dp[v] = min(dp[v], dp[v - moeda] + 1) ``` Na contagem de combinações, `dp[0] = 1`: existe exatamente uma forma de formar zero, que é não escolher moeda alguma. Cada moeda transfere suas combinações para os valores seguintes: ```text dp[0] = 1 dp[v] += dp[v - moeda] ``` ## Por que não escolher sempre a maior moeda? Uma estratégia gulosa parece natural: escolha a maior moeda possível e repita. Ela funciona para determinados sistemas monetários, mas não é correta para qualquer entrada. Considere moedas `[1, 3, 4]` e valor `6`: - guloso: `4 + 1 + 1`, total de 3 moedas; - solução ótima: `3 + 3`, total de 2 moedas. A programação dinâmica examina as melhores respostas intermediárias e encontra `3 + 3`. Portanto, quando as denominações vêm da entrada do programa ou não possuem uma propriedade matemática conhecida, DP é a escolha segura. ## Mínimo de moedas em Zig A função abaixo devolve `null` quando o valor não pode ser formado. Moedas de valor zero são ignoradas, pois não fazem o estado avançar. ```zig const std = @import("std"); const Allocator = std.mem.Allocator; const INF: u32 = std.math.maxInt(u32) / 2; pub fn minMoedas( allocator: Allocator, moedas: []const u32, valor: u32, ) !?u32 { const alvo: usize = @intCast(valor); const dp = try allocator.alloc(u32, alvo + 1); defer allocator.free(dp); @memset(dp, INF); dp[0] = 0; for (1..alvo + 1) |atual| { for (moedas) |moeda| { if (moeda == 0) continue; const m: usize = @intCast(moeda); if (m <= atual and dp[atual - m] < INF) { dp[atual] = @min(dp[atual], dp[atual - m] + 1); } } } return if (dp[alvo] == INF) null else dp[alvo]; } ``` Para moedas `[1, 5, 10, 25]` e alvo `30`, alguns estados importantes são: ```text dp[0] = 0 dp[5] = 1 dp[10] = 1 dp[25] = 1 dp[30] = 2 ``` O array informa a quantidade mínima, mas ainda não revela quais moedas foram escolhidas. Para reconstruir a solução, precisamos guardar a última moeda que melhorou cada estado. ## Reconstruindo as moedas escolhidas `ultima[atual]` registra a moeda usada quando encontramos uma solução menor para `atual`. Depois de preencher a tabela, caminhamos do alvo até zero. ```zig pub fn minMoedasDetalhado( allocator: Allocator, moedas: []const u32, valor: u32, ) !?[]u32 { const alvo: usize = @intCast(valor); const dp = try allocator.alloc(u32, alvo + 1); defer allocator.free(dp); const ultima = try allocator.alloc(u32, alvo + 1); defer allocator.free(ultima); @memset(dp, INF); @memset(ultima, 0); dp[0] = 0; for (1..alvo + 1) |atual| { for (moedas) |moeda| { if (moeda == 0) continue; const m: usize = @intCast(moeda); if (m <= atual and dp[atual - m] < INF and dp[atual - m] + 1 < dp[atual]) { dp[atual] = dp[atual - m] + 1; ultima[atual] = moeda; } } } if (dp[alvo] == INF) return null; var resultado = std.ArrayList(u32).init(allocator); errdefer resultado.deinit(); var restante = alvo; while (restante > 0) { const moeda = ultima[restante]; try resultado.append(moeda); restante -= @intCast(moeda); } return try resultado.toOwnedSlice(); } ``` O slice devolvido pertence ao chamador. Isso é importante em Zig: quem chama `minMoedasDetalhado` deve liberar o resultado com o mesmo allocator. ```zig if (try minMoedasDetalhado(allocator, &moedas, 30)) |usadas| { defer allocator.free(usadas); // usadas contém 25 e 5 para este exemplo } ``` ## Contando combinações de moedas Para contar combinações sem considerar a ordem, percorremos as moedas no loop externo. Assim, a combinação `1 + 5` não é contada novamente como `5 + 1`. ```zig pub fn contarCombinacoes( allocator: Allocator, moedas: []const u32, valor: u32, ) !u64 { const alvo: usize = @intCast(valor); const dp = try allocator.alloc(u64, alvo + 1); defer allocator.free(dp); @memset(dp, 0); dp[0] = 1; for (moedas) |moeda| { if (moeda == 0) continue; const m: usize = @intCast(moeda); if (m > alvo) continue; var atual = m; while (atual <= alvo) : (atual += 1) { dp[atual] = std.math.add( u64, dp[atual], dp[atual - m], ) catch return error.ContagemExcedida; } } return dp[alvo]; } ``` Com moedas `[1, 5, 10]` e valor `10`, existem quatro combinações: ```text 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 5 + 1 + 1 + 1 + 1 + 1 5 + 5 10 ``` A verificação com `std.math.add` evita que uma entrada grande faça a contagem ultrapassar o limite de `u64` silenciosamente. Nesse caso, a função devolve `error.ContagemExcedida`. ## Combinações versus permutações A ordem dos loops é uma das armadilhas mais comuns no Coin Change. ### Moedas no loop externo: combinações ```text para cada moeda: para cada valor de moeda até V: dp[valor] += dp[valor - moeda] ``` Aqui, `1 + 2` e `2 + 1` representam a mesma escolha e são contadas uma única vez. ### Valores no loop externo: sequências ordenadas ```text para cada valor de 1 até V: para cada moeda: dp[valor] += dp[valor - moeda] ``` Aqui, `1 + 2` e `2 + 1` são resultados diferentes. Essa variante é útil quando a ordem representa decisões distintas, mas não responde à pergunta tradicional de combinações de troco. Antes de implementar, escreva em uma frase o que deve ser contado. Isso evita alterar os loops e obter um número plausível, porém semanticamente errado. ## Testes para os casos principais Os testes devem cobrir uma resposta normal, um alvo impossível, valor zero e o contraexemplo da estratégia gulosa. ```zig test "encontra o mínimo de moedas" { const moedas = [_]u32{ 1, 5, 10, 25 }; const resultado = try minMoedas( std.testing.allocator, &moedas, 30, ); try std.testing.expectEqual(@as(?u32, 2), resultado); } test "supera a escolha gulosa" { const moedas = [_]u32{ 1, 3, 4 }; const resultado = try minMoedas( std.testing.allocator, &moedas, 6, ); try std.testing.expectEqual(@as(?u32, 2), resultado); } test "devolve null quando não existe solução" { const moedas = [_]u32{ 3, 7 }; const resultado = try minMoedas( std.testing.allocator, &moedas, 5, ); try std.testing.expectEqual(@as(?u32, null), resultado); } test "conta combinacoes sem considerar ordem" { const moedas = [_]u32{ 1, 5, 10 }; const total = try contarCombinacoes( std.testing.allocator, &moedas, 10, ); try std.testing.expectEqual(@as(u64, 4), total); } ``` Em um arquivo local, coloque `const std`, `Allocator`, `INF` e as funções antes dos testes. Execute com `zig test coin_change.zig` usando uma versão do compilador compatível com as APIs empregadas pelo projeto. ## Complexidade de tempo e memória | Variante | Tempo | Espaço auxiliar | Reconstrói solução? | |---|---:|---:|---| | Mínimo de moedas | O(n × V) | O(V) | não | | Mínimo detalhado | O(n × V) | O(V) | sim | | Contagem de combinações | O(n × V) | O(V) | não | Uma tabela bidimensional `dp[moeda][valor]` também resolve o problema, mas usa O(n × V) de memória. Como cada transição depende de estados da mesma linha, o slice unidimensional é suficiente para estas variantes. O custo depende do valor numérico `V`, não apenas da quantidade de dígitos usada para representá-lo. Por isso, o algoritmo é chamado de **pseudopolinomial**. Um alvo de milhões pode exigir tempo e memória consideráveis mesmo com poucas moedas. ## Erros comuns no problema do troco 1. **Usar guloso sem provar que o sistema de moedas permite.** Para denominações arbitrárias, ele pode perder a solução ótima. 2. **Confundir combinações com permutações.** A ordem dos loops define o que será contado. 3. **Inicializar todos os estados com zero no mínimo de moedas.** Estados ainda inalcançáveis precisam de um sentinela como `INF`. 4. **Somar a partir de um estado inalcançável.** Verifique `dp[atual - m] < INF` antes de adicionar 1. 5. **Aceitar moeda zero.** Ela não reduz o valor restante e pode invalidar transições ou reconstruções. 6. **Esquecer a propriedade do slice retornado.** A lista reconstruída deve ser liberada pelo chamador. 7. **Ignorar overflow na contagem.** O número de combinações pode crescer rapidamente. ## Quando usar Coin Change O padrão aparece além de moedas: composição de capacidade com tamanhos permitidos, seleção ilimitada de pacotes, contagem de formas de atingir uma pontuação e problemas de entrevistas sobre programação dinâmica. Ele se aproxima do **unbounded knapsack**, pois cada denominação pode ser usada repetidas vezes. Se cada item puder ser usado apenas uma vez, o problema muda. Nesse caso, percorra os valores em ordem decrescente ou use uma formulação de mochila 0/1. Para consolidar os fundamentos antes de avançar, veja também [Fibonacci com programação dinâmica](/algoritmos/fibonacci-dp/) e Edit Distance em Zig. ## Resumo Para resolver Coin Change em Zig: - use `dp[v]` como a melhor resposta para cada valor intermediário; - inicialize `dp[0]` de acordo com a variante; - use O(n × V) de tempo e O(V) de memória; - percorra moedas primeiro ao contar combinações; - mantenha uma tabela `ultima` se precisar reconstruir as moedas; - trate valor impossível, moeda zero, propriedade de memória e overflow. Essa estrutura produz uma solução clara, testável e aplicável tanto ao mínimo de moedas quanto à contagem de combinações.