24 de Março
Troco com moedas
Como sair da tentativa cega de combinações e montar uma programação dinamica que procura o menor custo para cada valor até o alvo.
Programação Dinamica Intermediario 25 min TypeScript
Dado um array coins com valores de moedas diferentes e um inteiro amount, retorne o menor número de moedas necessário para formar amount.
Se não for possível formar esse valor, retorne -1.
Você pode usar cada moeda quantas vezes quiser.
Exemplo:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Porque 11 = 5 + 5 + 1.
O que perceber antes de codar
- O objetivo e minimizar quantidade, não contar combinações.
- Cada valor menor que `amount` pode virar subproblema.
- Se um valor intermediario for impossivel, ele não ajuda a montar valores maiores.
Erros comuns
- tratar o problema como contagem de formas
- esquecer de marcar estados impossiveis com um valor sentinela
Passo 1 - Traduzir o que realmente esta sendo pedido
Esse problema parece de combinação.
Mas o enunciado não pergunta:
- quantas formas existem
Ele pergunta:
- qual e o menor número de moedas
Isso muda o tipo de estado.
Passo 2 - Escrever a versão inicial recursiva
A versão inicial natural e:
- para o valor atual, tente cada moeda
- resolva recursivamente o valor restante
- pegue o menor resultado valido
Funciona.
Mas recalcula os mesmos restos várias vezes.
Passo 3 - Definir o estado certo
A pergunta boa vira:
- qual e o menor número de moedas para montar cada valor de
0atéamount?
Isso sugere:
dp[value] = menor numero de moedas para formar value
Passo 4 - Montar a transição
Se você esta calculando value e tenta usar uma moeda coin, sobra:
value - coin
Se esse resto era possível, a nova resposta candidata vira:
dp[value - coin] + 1
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function coinChange(coins: number[], amount: number): number {
// sua solução aqui
return -1
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(amount * coins.length)
Espaço: O(amount)
Solução 1 - Recursao tentando todas as moedas antes de memoization
Boa versão inicial para deixar o subproblema visível.
export function coinChange(coins: number[], amount: number): number {
function solve(remaining: number): number {
if (remaining === 0) {
return 0
}
if (remaining < 0) {
return Infinity
}
let best = Infinity
for (const coin of coins) {
best = Math.min(best, solve(remaining - coin) + 1)
}
return best
}
const answer = solve(amount)
return Number.isFinite(answer) ? answer : -1
}O problema aqui não e a ideia. E o retrabalho.
Solução 2 - Programacao dinamica de baixo para cima com estado 1D
Agora cada valor e resolvido uma vez.
export function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0
for (let value = 1; value <= amount; value += 1) {
for (const coin of coins) {
if (coin <= value) {
dp[value] = Math.min(dp[value], dp[value - coin] + 1)
}
}
}
return Number.isFinite(dp[amount]) ? dp[amount] : -1
}O raciocínio forte aqui e montar a resposta dos valores menores para os maiores.
O que dizer na entrevista
Uma explicação curta e boa seria:
O problema e de minimização, não de contagem. Entao eu defino
dp[value]como o menor número de moedas para formar aquele valor. Para cada valor, testo cada moeda e tento melhorar a resposta usandodp[value - coin] + 1. No fim, se o estado final continuar impossivel, devolvo-1.
Isso mostra que você:
- escolheu o estado certo
- separou bem caso impossivel de caso valido
- explicou a transição sem decorar formula
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- minimizar custo ou quantidade
- montar resposta em
programacao dinamica1D - reutilizar subproblemas por valor
- distinguir “não existe resposta” de “resposta grande”
O ponto não e decorar
coinChange.
O ponto e aprender a modelar minimização em
programacao dinamica.