Você recebe os valores das moedas disponíveis em moedas e um valor alvo A. Existe uma
quantidade ilimitada de cada moeda. Retorne o menor número de moedas cuja soma dá exatamente
A. Se não houver como formar o valor, retorne -1.
Exemplo 1 · moedas = [1, 3, 4], A = 6 → 2
3 + 3 = 6. O guloso (sempre a maior moeda que cabe) erra: 4 + 1 + 1 usa 3 moedas. Por isso precisamos de DP.
Exemplo 2 · moedas = [2], A = 3 → -1
Só com moedas de 2 nunca se chega a um valor ímpar.
Tabulation: dp[i][a] = menor número de moedas para formar a usando
só as primeiras i moedas (∞ = impossível). É um knapsack ilimitado:
sem a moeda lê a linha de cima (dp[i-1][a]), mas com ela lê a mesma linha
(dp[i][a - moeda] + 1), que já pode ter usado essa moeda. No knapsack 0/1
as duas leituras vêm da linha de cima.
tempo O(n·A)espaço O(n·A)
n moedas × A + 1 valores, cada célula em O(1).
moedas
moeda da vez
registradores
tabela dp[i][a]
leitura · sem a moeda (cima)leitura · com a moeda (mesma linha)escrita░░ não inicializado · ∞ impossível
código
memória · bloco contíguo row-major
A linha i começa em base + i·(A+1)·4. ∞ na prática é um número sentinela grande (ex.: A + 1).
Custo: O(n·A) de espaço.
O mesmo da versão com matriz em um único array de A + 1 células.
Aqui a vai para frente, o contrário do knapsack 0/1:
quando lemos dp[a - moeda], ele já foi atualizado nesta rodada, ou seja, já pode conter a moeda atual.
É exatamente isso que permite usar a mesma moeda várias vezes.
tempo O(n·A)espaço O(A)
Uma linha só, percorrida para frente.
moedas
moeda da vez
registradores
array dp[a]
leitura · dp[a] antigo (sem a moeda)leitura · dp[a − moeda] (com a moeda)escritai=k rodada que escreveu a célula
código
memória · O(A)
A matriz aloca (n+1)·(A+1) = 28 células (112 B). Aqui são só A+1 = 7 (28 B), qualquer que seja
o número de moedas.
Memoization (top-down): f(a) = menor número de moedas para formar a.
Como qualquer moeda pode ser usada a qualquer momento, o estado é só o valor: o memo tem
uma dimensão. f(a) tenta cada moeda como a primeira e pede f(a - m). Valores como
f(2) são pedidos por vários caminhos (6→5→2, 6→3→2...), então viram cache hits.
tempo O(n·A)espaço O(A)
A + 1 estados f(a), cada um testa as n moedas. Memo de A + 1 células e call stack de até A frames (moeda 1).
moedas
moeda da vez
registradores
memo[a]
leitura · cache hitescrita░░ nunca calculado
código
call stack
memória · heap (memo)
memo[0] nunca é gravado: o caso base devolve 0 direto. A stack pode chegar a A + 1 frames
(usando sempre a moeda 1), por isso valores grandes de A estouram a pilha nesta versão.