O desafio consistia em escrever uma função que, recebendo um número inteiro (de 1 a 250), retorna o menor número de moedas necessárias para somar a esse valor, utilizando as moedas de 1, 5, 7, 9 e 11

. O objetivo é encontrar a combinação de moedas que resulte no número de entrada com a menor quantidade total de moedas.

Detalhes do Desafio:

• Entrada: Um número inteiro num entre 1 e 250.
• Saída: O menor número de moedas cuja soma é igual a num.
• Moedas disponíveis: 1, 5, 7, 9 e 11.

Exemplo:

• Se num for 16, a saída deve ser 2 (usando 9 e 7).
• Se num for 25, a saída deve ser 3 (usando 11, 9 e 5, ou 9, 9 e 7).

Ajuda do CHATGPT - explicação com DYNAMIC PROGRAMING (DP)

1️⃣ Olhando para o problema

Imagine o problema:

“Eu quero formar um valor target usando o menor número de moedas de valores diferentes que tenho.”

Se você pensar bem, é um problema de decisões sobre subproblemas menores:

• Para formar 12 reais, posso:
  • Usar a moeda 1 → sobra 11
  • Usar a moeda 5 → sobra 7
  • Usar a moeda 11 → sobra 1

Cada escolha depende do melhor jeito de formar o resto.

💡 Percebeu? O que acontece para i depende de como resolvemos i - coin antes.

2️⃣ Como nasceu o raciocínio do DP