---
title: "Problema do Troco de Moedas em Rust"
url: "https://rustlang.com.br/algoritmos/coin-change/"
markdown_url: "https://rustlang.com.br/algoritmos/coin-change.MD"
description: "Resolva o problema do troco de moedas em Rust com programação dinâmica: mínimo de moedas, contagem de formas e relação com mochila ilimitada."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Problema do Troco de Moedas em Rust

Resolva o problema do troco de moedas em Rust com programação dinâmica: mínimo de moedas, contagem de formas e relação com mochila ilimitada.


O **problema do troco de moedas** é um clássico de programação dinâmica com aplicação direta no mundo real: dado um conjunto de denominações de moedas e um valor alvo, qual o número mínimo de moedas necessárias para atingir exatamente esse valor? Esse problema aparece em caixas eletrônicos, sistemas de pagamento, alocação de recursos e como base para entender a mochila ilimitada (unbounded knapsack).

Nesta página, implementamos duas variantes em Rust: **mínimo de moedas** (otimização) e **contagem de formas** (combinatória), com visualizações do array DP e análise completa.

## O Problema

### Variante 1: Mínimo de Moedas

**Entrada**: Um conjunto de denominações `moedas[]` e um valor `alvo`.

**Objetivo**: Encontrar o número mínimo de moedas que somam exatamente `alvo`. Cada denominação pode ser usada quantas vezes quiser. Se for impossível, retornar -1.

### Variante 2: Contagem de Formas

**Objetivo**: Contar de quantas maneiras distintas podemos formar o valor `alvo`.

**Exemplo:**

```
Moedas: [1, 5, 10, 25]
Alvo: 30

Variante 1 (mínimo): 2 moedas (25 + 5)
Variante 2 (formas): diversas combinações:
  30x1, 25x1+5x1, 25x1+5x1, 20x1+10x1, ...
```

## Abordagem Ingênua (Força Bruta)

Tentamos todas as combinações recursivamente:

```rust
/// Força bruta: testa todas as combinações de moedas.
/// Complexidade: O(n^(alvo/menor_moeda)) — exponencial.
fn troco_bruta(moedas: &[u32], alvo: u32) -> i32 {
    if alvo == 0 {
        return 0;
    }

    let mut melhor = i32::MAX;

    for &moeda in moedas {
        if moeda <= alvo {
            let resultado = troco_bruta(moedas, alvo - moeda);
            if resultado >= 0 && resultado + 1 < melhor {
                melhor = resultado + 1;
            }
        }
    }

    if melhor == i32::MAX { -1 } else { melhor }
}

fn main() {
    let moedas = [1, 5, 10, 25];
    let alvo = 30;
    println!("Mínimo de moedas: {}", troco_bruta(&moedas, alvo)); // 2
}
```

O problema é que o mesmo valor intermediário é recalculado inúmeras vezes. Por exemplo, para alcançar o valor 15, a recursão pode chegar a ele por `25 -> 15`, `10 + 5 -> 15`, `10 + 1*5 -> 15`, etc.

## Identificando Subestrutura Ótima

### Para o mínimo de moedas:

```
dp[v] = número mínimo de moedas para formar o valor v

dp[0] = 0  (zero moedas para valor zero)
dp[v] = min(dp[v - moeda] + 1) para cada moeda <= v
```

### Para a contagem de formas:

```
dp[v] = número de formas de formar o valor v

dp[0] = 1  (uma forma: não usar nenhuma moeda)
Para cada moeda c:
    dp[v] += dp[v - c]  para v >= c
```

Ambas as variantes satisfazem:
- **Subestrutura ótima**: a solução ótima para `v` se constrói a partir de soluções para `v - moeda`.
- **Subproblemas sobrepostos**: o mesmo valor intermediário é acessado múltiplas vezes.

**Relação com mochila ilimitada**: o troco de moedas é essencialmente uma mochila ilimitada onde os "pesos" são as denominações e o objetivo é minimizar o número de itens (ou contar combinações).

## Visualização da Tabela DP

Para moedas `[1, 3, 4]` e alvo `6` (mínimo de moedas):

```
Valor:     0   1   2   3   4   5   6
         +---+---+---+---+---+---+---+
dp:      | 0 | INF INF INF INF INF INF|  (inicialização)
         +---+---+---+---+---+---+---+

Processando moeda = 1:
dp:      | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

Processando moeda = 3:
  dp[3] = min(dp[3], dp[3-3]+1) = min(3, 0+1) = 1
  dp[4] = min(dp[4], dp[4-3]+1) = min(4, 1+1) = 2
  dp[5] = min(dp[5], dp[5-3]+1) = min(5, 2+1) = 3
  dp[6] = min(dp[6], dp[6-3]+1) = min(6, 3+1) = 2  (duas moedas de 3!)
dp:      | 0 | 1 | 2 | 1 | 2 | 3 | 2 |

Processando moeda = 4:
  dp[4] = min(dp[4], dp[4-4]+1) = min(2, 0+1) = 1
  dp[5] = min(dp[5], dp[5-4]+1) = min(3, 1+1) = 2
  dp[6] = min(dp[6], dp[6-4]+1) = min(2, 2+1) = 2
dp:      | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
                           ^           ^
                        1x moeda 4   mínimo: 2 moedas (3+3 ou 4+1+1)

Resultado: dp[6] = 2
```

Para a contagem de formas com moedas `[1, 2, 5]` e alvo `5`:

```
Valor:        0   1   2   3   4   5
            +---+---+---+---+---+---+
Inicial:    | 1 | 0 | 0 | 0 | 0 | 0 |

Após moeda=1:| 1 | 1 | 1 | 1 | 1 | 1 |  (só com moedas de 1)

Após moeda=2:| 1 | 1 | 2 | 2 | 3 | 3 |  (com moedas de 1 e 2)

Após moeda=5:| 1 | 1 | 2 | 2 | 3 | 4 |  (com moedas de 1, 2 e 5)

Resultado: 4 formas de dar troco para 5:
  [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]
```

## Complexidade

| Abordagem | Tempo | Espaço | Observação |
|-----------|-------|--------|------------|
| Força Bruta | O(n^(V/min_c)) | O(V) pilha | n = qtd moedas, V = alvo |
| Top-Down (Memoização) | O(n * V) | O(V) cache | n = qtd moedas |
| Bottom-Up (Tabulação) | O(n * V) | O(V) | Iterativo, vetor 1D |
| Otimizado | O(n * V) | O(V) | Já é a versão otimizada! |

## Implementação: Top-Down (Memoização)

```rust
use std::collections::HashMap;

/// Mínimo de moedas com memoização.
fn troco_memo(moedas: &[u32], alvo: u32, cache: &mut HashMap<u32, i32>) -> i32 {
    // Caso base: valor zero requer zero moedas
    if alvo == 0 {
        return 0;
    }

    // Verifica cache
    if let Some(&valor) = cache.get(&alvo) {
        return valor;
    }

    let mut melhor = i32::MAX;

    // Tenta cada denominação
    for &moeda in moedas {
        if moeda <= alvo {
            let sub = troco_memo(moedas, alvo - moeda, cache);
            if sub >= 0 && sub + 1 < melhor {
                melhor = sub + 1;
            }
        }
    }

    let resultado = if melhor == i32::MAX { -1 } else { melhor };
    cache.insert(alvo, resultado);
    resultado
}

fn main() {
    let moedas = vec![1, 5, 10, 25];
    let alvo = 30;

    let mut cache = HashMap::new();
    let resultado = troco_memo(&moedas, alvo, &mut cache);
    println!("Mínimo de moedas para {}: {}", alvo, resultado); // 2

    cache.clear();
    let alvo2 = 11;
    let moedas2 = vec![3, 5];
    let resultado2 = troco_memo(&moedas2, alvo2, &mut cache);
    println!("Mínimo para {} com {:?}: {}", alvo2, moedas2, resultado2); // 3 (5+3+3)

    cache.clear();
    let moedas3 = vec![2];
    let resultado3 = troco_memo(&moedas3, 3, &mut cache);
    println!("Mínimo para 3 com [2]: {}", resultado3); // -1 (impossível)
}
```

## Implementação: Bottom-Up (Tabulação)

### Variante 1: Mínimo de Moedas

```rust
/// Mínimo de moedas com tabulação bottom-up.
/// Retorna o número mínimo de moedas ou None se impossível.
fn troco_minimo(moedas: &[u32], alvo: usize) -> Option<usize> {
    // dp[v] = mínimo de moedas para formar o valor v
    // Usamos usize::MAX como "infinito" (impossível)
    let mut dp = vec![usize::MAX; alvo + 1];
    dp[0] = 0; // Caso base: zero moedas para valor zero

    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX {
                dp[v] = dp[v].min(dp[v - c] + 1);
            }
        }
    }

    if dp[alvo] == usize::MAX {
        None
    } else {
        Some(dp[alvo])
    }
}

fn main() {
    let moedas = vec![1, 5, 10, 25];

    for alvo in [6, 11, 15, 30, 99] {
        match troco_minimo(&moedas, alvo) {
            Some(n) => println!("Troco para {}: {} moedas", alvo, n),
            None => println!("Troco para {}: impossível", alvo),
        }
    }
    // Troco para 6: 2 moedas (5+1)
    // Troco para 11: 2 moedas (10+1)
    // Troco para 15: 2 moedas (10+5)
    // Troco para 30: 2 moedas (25+5)
    // Troco para 99: 8 moedas (25+25+25+10+10+1+1+1+1)
}
```

### Variante 2: Contagem de Formas

```rust
/// Conta o número de formas distintas de dar troco.
/// IMPORTANTE: iterar moedas no laço externo evita contar permutações.
fn contar_formas(moedas: &[u32], alvo: usize) -> u64 {
    let mut dp = vec![0u64; alvo + 1];
    dp[0] = 1; // Uma forma de dar troco para 0: não usar moedas

    // Para cada moeda, atualiza todos os valores que ela pode alcançar
    for &moeda in moedas {
        let c = moeda as usize;
        for v in c..=alvo {
            dp[v] += dp[v - c];
        }
    }

    dp[alvo]
}

fn main() {
    let moedas = vec![1, 2, 5];
    let alvo = 5;

    let formas = contar_formas(&moedas, alvo);
    println!("Formas de dar troco para {}: {}", alvo, formas); // 4

    // Moedas brasileiras: 5, 10, 25, 50 centavos; 1 real
    let reais = vec![5, 10, 25, 50, 100];
    let valor = 100; // 1 real em centavos
    let formas_real = contar_formas(&reais, valor);
    println!("Formas de trocar R$1,00: {}", formas_real);
}
```

**Atenção ao ordenamento dos laços**: Na contagem de formas, o laço externo itera sobre moedas e o interno sobre valores. Se invertermos, contaríamos **permutações** em vez de **combinações** (por exemplo, [1,2] e [2,1] seriam contados como formas distintas).

## Otimização de Espaço

As soluções bottom-up já usam apenas O(V) de espaço --- um único vetor unidimensional. Esta é a versão natural otimizada para o problema do troco, diferente de problemas como a mochila 0/1 que começam com tabela 2D.

Para a versão com memoização, o espaço também é O(V) pois o cache armazena no máximo V+1 entradas.

## Reconstruindo a Solução

Para saber **quais moedas** foram usadas:

```rust
/// Reconstrói quais moedas foram usadas para o troco mínimo.
fn reconstruir_troco(moedas: &[u32], alvo: usize) -> Option<Vec<u32>> {
    let mut dp = vec![usize::MAX; alvo + 1];
    // moeda_usada[v] = qual moeda foi usada para chegar ao valor v
    let mut moeda_usada = vec![0u32; alvo + 1];
    dp[0] = 0;

    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX && dp[v - c] + 1 < dp[v] {
                dp[v] = dp[v - c] + 1;
                moeda_usada[v] = moeda;
            }
        }
    }

    if dp[alvo] == usize::MAX {
        return None;
    }

    // Reconstrói a lista de moedas
    let mut resultado = Vec::new();
    let mut restante = alvo;
    while restante > 0 {
        let moeda = moeda_usada[restante];
        resultado.push(moeda);
        restante -= moeda as usize;
    }

    Some(resultado)
}

fn main() {
    let moedas = vec![1, 5, 10, 25];

    for alvo in [30, 41, 99] {
        match reconstruir_troco(&moedas, alvo) {
            Some(usadas) => {
                println!("Troco para {}: {} moedas -> {:?}", alvo, usadas.len(), usadas);
            }
            None => println!("Troco para {}: impossível", alvo),
        }
    }
    // Troco para 30: 2 moedas -> [25, 5]
    // Troco para 41: 4 moedas -> [25, 10, 5, 1]
    // Troco para 99: 8 moedas -> [25, 25, 25, 10, 10, 1, 1, 1, 1]
}
```

### Comparação: Abordagem Gulosa versus DP

Para moedas canônicas (como as brasileiras ou americanas), a abordagem gulosa funciona: sempre escolha a maior moeda possível. Mas nem sempre!

```rust
/// Abordagem gulosa: funciona para moedas canônicas, falha para outras.
fn troco_guloso(moedas: &mut [u32], alvo: u32) -> Option<Vec<u32>> {
    moedas.sort_unstable_by(|a, b| b.cmp(a)); // Ordena decrescente
    let mut restante = alvo;
    let mut resultado = Vec::new();

    for &moeda in moedas.iter() {
        while moeda <= restante {
            resultado.push(moeda);
            restante -= moeda;
        }
    }

    if restante == 0 {
        Some(resultado)
    } else {
        None
    }
}

fn main() {
    // Caso onde guloso funciona
    let mut moedas1 = vec![1, 5, 10, 25];
    println!("Guloso para 30: {:?}", troco_guloso(&mut moedas1, 30));
    // Some([25, 5]) — correto!

    // Caso onde guloso FALHA
    let mut moedas2 = vec![1, 3, 4];
    println!("Guloso para 6: {:?}", troco_guloso(&mut moedas2, 6));
    // Some([4, 1, 1]) = 3 moedas — ERRADO!
    // DP encontra: [3, 3] = 2 moedas

    let moedas3 = vec![1, 3, 4];
    match reconstruir_troco(&moedas3, 6) {
        Some(r) => println!("DP para 6: {:?} = {} moedas", r, r.len()),
        None => println!("Impossível"),
    }
}

fn reconstruir_troco(moedas: &[u32], alvo: usize) -> Option<Vec<u32>> {
    let mut dp = vec![usize::MAX; alvo + 1];
    let mut moeda_usada = vec![0u32; alvo + 1];
    dp[0] = 0;
    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX && dp[v - c] + 1 < dp[v] {
                dp[v] = dp[v - c] + 1;
                moeda_usada[v] = moeda;
            }
        }
    }
    if dp[alvo] == usize::MAX { return None; }
    let mut resultado = Vec::new();
    let mut restante = alvo;
    while restante > 0 {
        resultado.push(moeda_usada[restante]);
        restante -= moeda_usada[restante] as usize;
    }
    Some(resultado)
}
```

## Exercícios Práticos

1. **Moedas com limite**: Cada denominação tem um número máximo de cópias disponíveis. Por exemplo, você tem 3 moedas de 1, 2 moedas de 5 e 1 moeda de 10. Modifique a solução para respeitar esses limites (bounded knapsack).

2. **Troco com menor número de denominações**: Em vez de minimizar o total de moedas, minimize o número de **denominações distintas** usadas.

3. **Verificar sistema canônico**: Dado um conjunto de moedas, determine se a abordagem gulosa sempre dá a resposta ótima. Dica: teste todos os valores até `moeda_max^2`.

4. **Probabilidade de troco**: Dado que a máquina de troco seleciona moedas uniformemente ao acaso (dentre as que cabem), qual a probabilidade de dar o troco mínimo? Simule com Monte Carlo.

## Veja Também

- [Vec — Vetores dinâmicos](/stdlib/vec/) — estrutura base para o array DP
- [Slice — Fatias](/stdlib/slice/) — iteração eficiente sobre moedas
- [Option — Valores opcionais](/stdlib/option/) — representação idiomática de "impossível"
- [Problema da Mochila](/algoritmos/knapsack/) — generalização do troco de moedas
- [Fibonacci com DP](/algoritmos/fibonacci-dp/) — introdução a programação dinâmica
- [Soma de Subconjuntos](/algoritmos/subset-sum/) — variante decisional relacionada