Algoritmi e Strutture Dati

Coin change – il numero di modi

Dato un sistema monetario composto da n monete, ognuna con un valore positivo , si vuole determinare il numero di modi per ottenere un importo totale pari a x utilizzando queste monete.
Ad esempio, se i valori delle monete sono e abbiamo bisogno di ottenere 5, ci sono 4 modi differenti per farlo: 5, 1 + 2 + 2, 1 + 1 + 1 + 2 e 1 + 1 + 1 + 1 + 1. A differenza di una “combination sum”, qui l’ordine non conta: ci interessa soltanto il multiset di monete utilizzate.

Dati in ingresso

La prima riga dell’input contiene due interi n (1 ≤ n ≤ 100) e x (1 ≤ x ≤ ).
La riga successiva contiene n numeri interi separati da spazio (1 ≤ ≤ ).

Dati in uscita

Il programma deve stampare il numero di modi possibili per ottenere x usando le monete date. Poiché la risposta può diventare molto grande, occorre stamparla modulo .

Esempi

Ingresso
Uscita
3 5 1 2 5
4
3 9 2 3 5
3

Spiegazione

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, e 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

Se consideriamo uno stato d[s] in cui d[s] rappresenta il numero di modi diversi per ottenere la somma s usando le monete, incorriamo nel problema del doppio conteggio: la stessa combinazione di monete verrebbe infatti contata più volte. Ad esempio, la combinazione 1 + 2 + 2 (che dovrebbe essere conteggiata una sola volta) verrebbe comunque calcolata in più modi (1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1).
Per eliminare questo inconveniente, calcoliamo il numero di modi per ottenere il valore s processando tutte le monete fino all’indice ci (dove ci è l’indice della moneta nell’array c). Possiamo decidere di non usare affatto la moneta ci oppure di usarla più volte: tutto ciò è racchiuso nello stato. Quindi, definiamo d[s][ci] come il numero di modi per ottenere la somma s usando tutte le monete fino a ci.
 
Esistono due possibili transizioni che ci conducono dagli stati precedenti a d[s][ci] (dove l’indice corrente è ci e il valore della moneta è val):
  1. Non utilizzare la moneta ci → d[s][ci - 1]
  1. Utilizzare la moneta ci per 0, 1, 2 … volte → d[s - val][ci]
In questo modo, il numero totale di modi per ottenere la somma s con tutte le monete fino a ci è la somma di tutte le transizioni provenienti dagli stati precedenti.
 
c = [...]
x = ...
# Inizializza d con (x+1) righe e len(c) colonne di 0
d = [[0] * len(c) for _ in range(x + 1)]
Iniziamo elaborando la prima moneta e aggiorniamo lo stato d[s][0] per tutte le somme s possibili usando quest’ultima. Poi passiamo alla seconda moneta e aggiorniamo tutti gli stati d[s][1], poi alla terza, e così via, fino all’ultima moneta.
Alla fine, il numero di modi per ottenere la somma x sarà nel valore d[x][len(c) - 1] dopo avere utilizzato tutte le monete:
for ci, val in enumerate(c):      # Itera sulle monete una alla volta
    d[0][ci] = 1                  # È possibile ottenere la somma 0 senza utilizzare alcuna moneta
    for s in range(1, x + 1):     # Itera su tutte le somme da 1 a x inclusi
        if ci - 1 >= 0:           # (1) Non utilizzare affatto ci
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Usare ci per 0 o più volte
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 Riesci a pensare a un modo per mantenere soltanto una lista monodimensionale per d?
Elaboriamo una moneta alla volta, quindi possiamo scartare tutti gli stati calcolati per la moneta ci - 2 e precedenti. A ogni iterazione, siamo interessati soltanto allo stato della moneta corrente ci e a quello della precedente ci - 1. Possiamo perciò salvare lo stato della moneta precedente in un array separato da quello della moneta corrente.
😎 Riesci a pensare a un modo per non utilizzare alcun array ausiliario e ricorrere a un unico array monodimensionale d?
Possiamo notare che l’unica operazione proveniente dallo stato della moneta precedente è l’addizione di prev[s] a d[s]. Quindi, possiamo evitare del tutto di memorizzare l’array precedente:
# Inizializza d con x+1 elementi
d = [1] + [0] * x                 # Possibile ottenere la somma 0 senza alcuna moneta

for ci, val in enumerate(c):      # Itera sulle monete una alla volta
    for s in range(1, x + 1):     # Itera su tutte le somme da 1 a x inclusi
        if s - val >= 0:          # (2) Usare ci per 0 o più volte
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue