dp[0] = 0
dp[v] = min(dp[v - moeda[i]] + 1) para cada moeda[i] <= v

Moedas: [1, 5, 10, 25]    Valor: 30

Mínimo de moedas para valor 30:
  dp[0]=0  dp[1]=1  dp[5]=1  dp[10]=1  dp[15]=2  dp[25]=1  dp[30]=2

  Resposta: 2 moedas (25 + 5)

Contagem de formas para valor 10:
  Moedas [1, 5, 10]:
  - 10×1                    = 10
  - 5×1 + 5                = 10
  - 5 + 5                   = 10
  - 10                      = 10
  Total: 4 formas

const std = @import("std");
const Allocator = std.mem.Allocator;

const INF: u32 = std.math.maxInt(u32) / 2;

/// Encontra o número mínimo de moedas para formar o valor alvo.
/// Retorna null se for impossível.
pub fn minMoedas(
    allocator: Allocator,
    moedas: []const u32,
    valor: u32,
) !?u32 {
    const v: usize = valor;
    const dp = try allocator.alloc(u32, v + 1);
    defer allocator.free(dp);
    @memset(dp, INF);
    dp[0] = 0;

    for (1..v + 1) |i| {
        for (moedas) |moeda| {
            if (moeda <= i and dp[i - moeda] < INF) {
                dp[i] = @min(dp[i], dp[i - moeda] + 1);
            }
        }
    }

    return if (dp[v] >= INF) null else dp[v];
}

/// Reconstrói quais moedas foram usadas.
pub fn minMoedasDetalhado(
    allocator: Allocator,
    moedas: []const u32,
    valor: u32,
) !?[]u32 {
    const v: usize = valor;
    const dp = try allocator.alloc(u32, v + 1);
    defer allocator.free(dp);
    const ultimo = try allocator.alloc(u32, v + 1);
    defer allocator.free(ultimo);

    @memset(dp, INF);
    @memset(ultimo, 0);
    dp[0] = 0;

    for (1..v + 1) |i| {
        for (moedas) |moeda| {
            if (moeda <= i and dp[i - moeda] < INF and dp[i - moeda] + 1 < dp[i]) {
                dp[i] = dp[i - moeda] + 1;
                ultimo[i] = moeda;
            }
        }
    }

    if (dp[v] >= INF) return null;

    // Reconstrói
    var resultado = std.ArrayList(u32).init(allocator);
    var restante = v;
    while (restante > 0) {
        try resultado.append(ultimo[restante]);
        restante -= ultimo[restante];
    }

    return try resultado.toOwnedSlice();
}

/// Conta o número de formas de formar o valor com as moedas dadas.
pub fn contarFormas(
    allocator: Allocator,
    moedas: []const u32,
    valor: u32,
) !u64 {
    const v: usize = valor;
    const dp = try allocator.alloc(u64, v + 1);
    defer allocator.free(dp);
    @memset(dp, 0);
    dp[0] = 1;

    // Percorre moedas primeiro para evitar contagem duplicada
    for (moedas) |moeda| {
        var j: usize = moeda;
        while (j <= v) : (j += 1) {
            dp[j] += dp[j - moeda];
        }
    }

    return dp[v];
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const moedas = [_]u32{ 1, 5, 10, 25 };
    const valor: u32 = 30;

    // Mínimo de moedas
    if (try minMoedas(allocator, &moedas, valor)) |min| {
        try stdout.print("Valor: {d} centavos\n", .{valor});
        try stdout.print("Mínimo de moedas: {d}\n", .{min});
    }

    // Detalhamento
    if (try minMoedasDetalhado(allocator, &moedas, valor)) |lista| {
        defer allocator.free(lista);
        try stdout.print("Moedas usadas: ", .{});
        for (lista) |m| try stdout.print("{d} ", .{m});
        try stdout.print("\n", .{});
    }

    // Contagem de formas
    const formas = try contarFormas(allocator, &moedas, valor);
    try stdout.print("Número de formas: {d}\n", .{formas});

    // Caso impossível
    const moedas2 = [_]u32{ 3, 7 };
    if (try minMoedas(allocator, &moedas2, 5)) |min| {
        try stdout.print("Valor 5 com moedas [3,7]: {d}\n", .{min});
    } else {
        try stdout.print("Valor 5 com moedas [3,7]: impossível\n", .{});
    }
}