Uma discussão sobre leetcode: problemas de mudança de moeda

A introdução como engenheiro de software, a preparação para entrevistas tornou -se mais importante do que nunca no cenário de tecnologia incerto de hoje. Entre os desafios dinâmicos de programação, os problemas de mudança de moeda são alguns dos mais complicados de manter uma aderência sólida – eles parecem simples no começo, mas são fáceis de esquecer. Neste artigo, divulgarei esses problemas de uma maneira que ajude os outros a abordá -los com confiança, além de reforçar meu próprio entendimento, para que a lógica fique com mais firmeza na próxima vez que eu os encontrar. A troca de moedas I Problem o problema da mudança de moeda solicita o número mínimo de moedas para atingir o valor solicitado. Você recebe moedas de matriz inteira, representando moedas de diferentes denominações e uma quantia inteira representando uma quantia total de dinheiro. Retorne o menor número de moedas necessárias para compensar esse valor. Se essa quantia de dinheiro não puder ser composta por nenhuma combinação das moedas, retorne -1. Você pode assumir que você tem um número infinito de cada tipo de moeda. Exemplo 1: entrada: moedas = [1,2,5]quantidade = 11, saída: 3, explicação: 11 = 5 + 5 + 1 Exemplo 2: entrada: moedas = [2]quantidade = 3, saída: -1 Exemplo 3: entrada: moedas = [1]quantidade = 0, saída: 0 Enquanto as soluções recursivas tendem a ser mais intuitivas, o método de tabulação oferece melhor legibilidade – o que é importante para ajudar os leitores a entender. A idéia por trás da solução é acompanhar o número mínimo de moedas para compensar todos os restos possíveis até o valor solicitado. Intuitivamente, quando entendemos que o objetivo é a minimização, podemos definir um valor padrão do número mínimo de moedas para cada restante como infinito. Usando o Python, isso é tão simples quanto usar o número Float (‘Inf’). Solução de classe: def coinchange (self, moedas: lista[int]quantidade: int) -> int: dp = [float(‘inf’)] * (Quantidade + 1) # … Digite o modo de saída do modo de tela cheia no snippet de código acima, podemos ver que estamos inicializando uma matriz cheia do número infinito para todos os seus membros. O tamanho da matriz é intencionalmente definido como quantidade + 1 para deixar um espaço para o índice 0 e deixar o restante dos índices representação idiomática dos restos. Isso significa que, quando queremos acessar o número mínimo de moedas para um determinado restante, podemos simplesmente buscá -las usando o número restante como seus índices. # … dp[0] = 0 # [0, inf, inf, inf, …]
# … Digite o modo de saída do modo de tela cheia em seguida, queremos definir manualmente o número mínimo de moedas para alcançar 0 restante como 0. Isso faz sentido como o número de moedas para alcançar nada é basicamente nada. Portanto, é o primeiro restante na matriz a obter um número de não infinidade. # … para eu no alcance (1, quantidade + 1): para moedas em moedas: se moedas> i: # pular se a moeda for maior que o restante continue candidato_min_coins = 1 + dp[i – coin]
# Compare o mínimo anterior com o candidato DP[i] = min (dp[i]candidato_min_coins) # … Digite o modo de saída de tela cheia de saída de tela cheia em andamento, mergulhamos no núcleo da solução. Podemos começar a fazer um loop e calcular o número mínimo de moedas para todos os restos possíveis, desde o menor até o valor solicitado. A lógica por trás do processo de computação envolve: verificação de cada moeda se a moeda é aplicável ao restante fornecido. Isso significa que a moeda não pode ser maior que o restante, caso contrário, não compensará o restante. A revisão do número mínimo de moedas para o restante fornecido se um número menor de moedas puder compensar a mesma quantidade. Esta etapa inclui a comparação do número mínimo anterior de moedas e o novo candidato. # … se dp[amount] == float (‘inf’): retornar -1 retornar dp[amount]

Digite o modo de saída do modo de tela cheia, em última análise, até o valor solicitado é tratado como um restante. Para que nossa solução produza sua resposta, podemos simplesmente obter o último membro da matriz de contagem mínima de moedas restantes. No entanto, ainda há uma chance de que o valor solicitado não possa ser construído por qualquer combinação das moedas fornecidas. Para lidar com isso, simplesmente verificamos se a resposta final é realmente algo menor que o infinito. O seguinte exibe a solução completa. Solução de classe: def coinchange (self, moedas: lista[int]quantidade: int) -> int: dp = [float(‘inf’)] * (quantidade + 1) DP[0] = 0 para i no intervalo (1, quantidade + 1): para moedas em moedas: se moedas> i: # pular se a moeda for maior que o restante continue candidato_min_coins = 1 + dp[i – coin]
# Compare o mínimo anterior com o candidato DP[i] = min (dp[i]candidato_min_coins) se DP[-1] == float (‘inf’): retornar -1 retornar dp[-1]

Digite o modo de saída do modo de tela cheia, o problema da alteração da moeda II O problema da alteração da moeda II solicita o número de maneiras de compensar uma quantidade usando as moedas fornecidas. Você recebe moedas de matriz inteira, representando moedas de diferentes denominações e uma quantia inteira representando uma quantia total de dinheiro. Retorne o número de combinações que compõem esse valor. Se essa quantia de dinheiro não puder ser composta por qualquer combinação das moedas, retorne 0. Você pode assumir que possui um número infinito de cada tipo de moeda. Exemplo 1: entrada: quantidade = 5, moedas = [1,2,5]Saída: 4explanation: Existem quatro maneiras de compensar a quantidade: 5 = 5, 5 = 2+2+1, 5 = 2+1+1+1, 5 = 1+1+1+1+1 novamente, a idéia por trás da solução é acompanhar os cálculos anteriores. No entanto, desta vez, mantemos um registro do número de maneiras de compensar todos os restos possíveis. O número de maneiras de compensar os restos menores determina o mesmo para os maiores. Iniciamos a solução inicializando valores padrão para o número de maneiras de compensar todos os restos possíveis. Queremos coletar o maior número possível de maneiras de compensar uma quantidade – isso indica que a direção da alteração do número é para cima. Portanto, o número padrão de maneiras é zero – um valor mínimo. Solução de classe: def mudança (self, quantidade: int, moedas: lista[int]) -> int: dp = [0] * (quantidade + 1) # [0,0,0,0,0,…]
# … Digite o modo de saída do modo de tela completa, podemos inicializar o número de maneiras de compensar o valor zero. Só há uma maneira de compensar a quantidade de zero. # … dp[0] = 1 # [1,0,0,0,0,…]
# … Digite o modo de saída do modo de tela cheia em andamento, queremos iterar para todos os tipos de moedas que temos. Para cada moeda, queremos avaliar todo o restante possível se a moeda pode compensar cada restante. No processo, uma contagem de restos que permanece zero nos informa que ele não pode ser compensado. Por outro lado, uma contagem restante que aumenta continuamente herdando a contagem de restantes menores mostra que é construível. Para moedas em moedas: para i no intervalo (1, quantidade + 1): dp[i] += dp[i – coin]

Digite o modo de saída do modo de tela cheia, finalmente, precisamos retornar o número de maneiras de construir o valor solicitado. Para entregar isso, podemos simplesmente obter a contagem do último elemento na matriz. A seguir, mostra a solução completa. Solução de classe: def mudança (self, quantidade: int, moedas: lista[int]) -> int: dp = [0] * (quantidade + 1) DP[0] = 1 para moedas em moedas: para eu no alcance (moeda, quantidade + 1): dp[i] += dp[i – coin]

retornar dp[amount]

Digite o modo de tela completa Sair do modo de tela cheia Conclusão Os problemas de mudança de moeda são problemas de programação dinâmica com algumas comparações e operações especiais que utilizam os cálculos anteriores. Os problemas de mudança de moeda são mais legíveis e fáceis de aprender usando o método de tabulação.

Fonte