Coin Change

Q: Qual é a complexidade de tempo do problema do troco?

A solução com programação dinâmica leva tempo O(amount × coins) e usa espaço O(amount) : uma entrada na tabela para cada valor, e cada moeda é verificada para cada entrada. A recursão simples sem memoização é exponencial em relação ao valor.

Q: Para o problema do Troco, é melhor a abordagem top-down ou bottom-up?

Ambos realizam o mesmo trabalho O(amount × coins) . A recursão top-down pode aninhar-se até a profundidade do valor, o que causa estouro da pilha de chamadas para 10^4 em várias linguagens. A abordagem bottom-up preenche a tabela com um loop, portanto não tem limite de profundidade e é a opção mais segura em uma entrevista.

MédioProgramação dinâmica

+10

Você recebe uma lista coins com diferentes valores de moedas e um valor-alvo amount. Você pode usar cada valor de moeda quantas vezes quiser. Retorne o menor número de moedas cujos valores somem exatamente amount, ou -1 se nenhuma combinação de moedas alcançar esse valor. Um valor de 0 precisa de 0 moedas.

Função

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: os diferentes valores das moedas, cada um podendo ser usado quantas vezes quiser
amountinteger: o total a pagar exatamente
Retornainteger: a menor quantidade de moedas necessária, ou -1 quando não for possível formar o valor

Restrições

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Todos os valores das moedas são diferentes.

Exemplos

Entrada: coins = [2, 5, 10]amount = 27
Saída: 4
Explicação: 10 + 10 + 5 + 2 totalizam 27 com quatro moedas. Três moedas não dão certo: 27 é ímpar, então precisam de exatamente uma moeda de 5, e as outras duas somam no máximo 20, menos que 22.

Para ir além

Você consegue contar quantas combinações diferentes de moedas somam amount, em vez de encontrar o menor número de moedas?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Pegar a maior moeda que cabe não funciona: com moedas de 1, 3 e 4, o valor 6 é pago como 4 + 1 + 1, enquanto 3 + 3 precisa de duas moedas. O menor número de moedas para um valor depende apenas do menor número de moedas para valores menores, então você resolve cada valor de 0 até amount uma vez.

Tente todas as combinações com recursão

Correta, mas não termina nos maiores testes

Intuição

Se a última moeda que você paga vale c, as moedas anteriores totalizam remaining - c da forma mais econômica possível. Portanto, fewest(remaining) é um a mais que o melhor fewest(remaining - c) entre todas as moedas que cabem. Isso tenta todas as sequências de moedas que não ultrapassam o valor, então não pode deixar de encontrar a melhor.

Ele resolve os mesmos valores repetidamente. Com moedas de 2, 5 e 10, o valor 27 chega a 15 depois de pagar 10 + 2, 2 + 10, 5 + 5 + 2 e outras combinações em ordens diferentes, e calcula 15 do zero a cada vez. O número de chamadas cresce exponencialmente com o valor.

Algoritmo

Escreva uma função auxiliar fewest(remaining) que retorne o menor número de moedas para remaining, ou -1 se nenhuma combinação funcionar.
Se remaining for 0, retorne 0.
Para cada moeda que não seja maior que remaining, chame a função auxiliar para o valor restante depois de pagar essa moeda.
Mantenha o menor resultado diferente de -1, mais uma moeda pela moeda que você pagou.
Retorne essa contagem, ou -1 se nenhuma moeda levar a uma solução. A resposta é fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Recursão com memoização

Correta, mas não termina nos maiores testes

Intuição

A recursão só pergunta sobre quantias de 0 a amount. Armazene cada resposta em um array na primeira vez que você a calcular e retorne o valor armazenado quando essa quantia aparecer novamente. Cada quantia é resolvida uma vez, com um loop sobre as moedas: trabalho de O(amount × coins).

As chamadas ainda se aninham em um nível por moeda paga. Com uma moeda de valor 1, isso pode chegar a 10^4 níveis, mais do que a pilha de chamadas padrão permite em muitas linguagens.

Algoritmo

Crie um array memo com espaço para todos os valores de 0 a amount, contendo um marcador que significa que ainda não foi calculado.
Em fewest(remaining), retorne 0 para 0 e retorne memo[remaining] se já houver uma resposta armazenada.
Caso contrário, tente cada moeda que caiba, como na recursão simples, e mantenha o menor resultado mais um.
Salve o resultado, inclusive -1, em memo[remaining] antes de retorná-lo.
Retorne fewest(amount).

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Programação dinâmica bottom-up para quantias

Intuição

Preencha uma tabela fewest começando em 0 e avançando. Quando chegar a um total t, todos os totais menores já estarão resolvidos, então fewest[t] é 1 a mais que o menor fewest[t-c] entre as moedas c que cabem.

Os totais que não podem ser alcançados com nenhuma combinação de moedas recebem o marcador amount + 1. Cada moeda vale pelo menos 1, então uma resposta válida nunca usa mais do que amount moedas, e o marcador perde em todas as comparações. Um loop substitui a recursão, então a profundidade da pilha de chamadas nunca importa.

Algoritmo

Crie fewest com amount + 1 entradas, todas definidas com o marcador amount + 1, e defina fewest[0] como 0.
Para cada total t de 1 a amount, examine cada moeda c com c ≤ t.
Se fewest[t-c] + 1 for menor que fewest[t], armazene-o em fewest[t].
Após o loop, retorne -1 se fewest[amount] ainda contiver o marcador; caso contrário, retorne fewest[amount].

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Armadilhas e casos extremos

Usar primeiro a moeda de maior valor. Com moedas de 3 e 5 e valor total de 9, o algoritmo usa 5 e 3, fica sem saída em 1 e retorna -1, enquanto 3 + 3 + 3 funciona.
Usar o maior inteiro como marcador. Somar 1 a ele causa um estouro para um número negativo, que então vence todas as comparações. Use amount + 1.
Somar 1 a um beco sem saída. Um ramo que retorna -1, somado à moeda usada, resulta em 0 e vence todas as comparações. Ignore os resultados -1.
Fazer a recursão descer amount níveis. Com uma moeda de valor 1 e valor total 10^4, Python para no limite padrão de 1000 níveis, e JavaScript, Dart, Ruby e R também ficam sem espaço na pilha.
Ler fewest[t-c] para uma moeda maior que t, antes do início da tabela.

Perguntas frequentes3

Por que a abordagem gulosa falha para o problema do troco?

Pegar a maior moeda que cabe é seguro apenas para alguns sistemas de moedas, como a maioria das moedas reais. Com moedas de 1, 3 e 4, paga 6 com três moedas em vez de duas, e com moedas de 3 e 5 não consegue pagar 9 de jeito nenhum. A programação dinâmica compara todas as opções, então nenhum sistema de moedas a engana.

Qual é a complexidade de tempo do problema do troco?

A solução com programação dinâmica leva tempo O(amount × coins) e usa espaço O(amount): uma entrada na tabela para cada valor, e cada moeda é verificada para cada entrada. A recursão simples sem memoização é exponencial em relação ao valor.

Para o problema do Troco, é melhor a abordagem top-down ou bottom-up?

Ambos realizam o mesmo trabalho O(amount × coins). A recursão top-down pode aninhar-se até a profundidade do valor, o que causa estouro da pilha de chamadas para 10^4 em várias linguagens. A abordagem bottom-up preenche a tabela com um loop, portanto não tem limite de profundidade e é a opção mais segura em uma entrevista.

def coinChange(coins, amount):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

coins = [2, 5, 10]
amount = 27

Saída Esperada

Coin Change

Função

Restrições

Exemplos

Dicas

Solução

Tente todas as combinações com recursão

Recursão com memoização

Programação dinâmica bottom-up para quantias

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos