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.

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:

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:

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.

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:

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.

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.

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.

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:

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

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

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.

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

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