Coin change - the number of ways
Dado um sistema monetário composto por
n moedas, em que cada moeda tem um valor positivo , pretende-se determinar o número de formas de obter um montante total de x utilizando essas moedas.Por exemplo, se os valores das moedas forem e precisarmos de obter
5, existem 4 formas diferentes de o conseguir: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, e 1 + 1 + 1 + 1 + 1. Ao contrário de uma combination sum tradicional, a ordem aqui não importa; estamos apenas interessados no multiconjunto de moedas que utilizamos.Input
A primeira linha do input contém dois inteiros
n (1 ≤ n ≤ 100) e x (1 ≤ x ≤ ).A linha seguinte contém
n inteiros separados por espaço (1 ≤ ≤ ).Output
O programa deve apresentar o número de formas possíveis de obter
x utilizando as moedas fornecidas. Dado que a resposta pode ser muito grande, deverá ser impressa módulo .Exemplos
Input | Output |
3 5
1 2 5 | 4 |
3 9
2 3 5 | 3 |
Explicação
5,1 + 2 + 2,1 + 1 + 1 + 2, e1 + 1 + 1 + 1 + 1
3 + 3 + 3,2 + 2 + 5,2 + 2 + 2 + 3
Tutorial
Repare que, se armazenarmos um estado
d[s] onde d[s] representa o número de formas de obter a soma s com as moedas, poderíamos contar o mesmo conjunto de moedas mais de uma vez. Por exemplo, para o conjunto 1 + 2 + 2 (que só deve ser contado uma vez), seria possível contabilizá-lo 3 vezes para todas as suas permutações: 1 + 2 + 2, 2 + 1 + 2, e 2 + 2 + 1.Para resolver esse problema, vamos considerar o número de maneiras de obter o valor
s processando todas as moedas até ci (onde ci é o índice da moeda no array c). Podemos escolher não usar a moeda ci ou usá-la várias vezes — tudo isso fica refletido no estado. Assim, nosso estado d[s][ci] representa o número de formas de obter a soma s ao processar todas as moedas até ci.Existem 2 transições possíveis para chegar a
d[s][ci] (assumindo que o índice da moeda atual é ci e o seu valor é val):- Não usar a moeda
ci→d[s][ci - 1]
- Usar a moeda
ci0, 1, 2, … k vezes →d[s - val][ci]
Portanto, o número total de formas de chegar à soma
s usando todas as moedas até ci é a soma de todas as transições mencionadas.c = [...]
x = ...
# Initialize d with x+1 rows and len(c) columns of 0s
d = [[0] * len(c) for _ in range(x + 1)]Podemos começar por processar a primeira moeda e atualizar o estado
d[s][0] para todas as somas possíveis de s usando apenas a primeira moeda. Depois, passamos para a segunda moeda e atualizamos todos os estados d[s][1], continuamos para a terceira (d[s][2]), e assim por diante, até processarmos a última moeda.Após processar todas as moedas, basta imprimir o número de formas de obter a soma
x, consultando o estado após processarmos a última moeda, d[x][len(c) - 1]:for ci, val in enumerate(c): # Iterate over coins one-by-one
d[0][ci] = 1 # Possible to obtain sum of 0 with no coins
for s in range(1, x + 1): # Iterate over all the sums 1...x inclusive
if ci - 1 >= 0: # (1) Not use ci at all
d[s][ci] += d[s][ci - 1]
if s - val >= 0: # (2) Use ci for 0+ times
d[s][ci] += d[s - val][ci]
print(d[x][len(c) - 1])😎 Consegue pensar numa forma de manter apenas um array unidimensional para d?
Processamos as moedas uma a uma. Por isso, podemos descartar todos os estados calculados para a moeda
ci - 2 e anteriores. Em cada iteração, só precisamos do estado da moeda atual ci e do estado da moeda anterior ci - 1. Logo, podemos armazenar o estado da moeda anterior num array e o da moeda atual noutro.😎 Consegue pensar numa forma de não usar nenhum array auxiliar e recorrer apenas a um d unidimensional?
Podemos reparar que a única operação que vem do estado da moeda anterior é a soma de
prev[s] a d[s]. Desta forma, não é necessário manter um array separado para a moeda anterior:# Initialize d x+1 items
d = [1] + [0] * x # Possible to obtain sum of 0 with no coins
for ci, val in enumerate(c): # Iterate over coins one-by-one
for s in range(1, x + 1): # Iterate over all the sums 1...x inclusive
if s - val >= 0: # (2) Use ci for 0+ times
d[s] += d[s - val]
d[s] %= MOD
print(d[x])Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB