numero di modi per rendere il cambiamento di importo N

Question

mi sono imbattuto in questo problema:

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Dato un valore N, se vogliamo fare il cambiamento per N centesimi, e noi abbiamo fornitura infinita di ognuna delle monete S = {S1, S2, .., Sm}, quanti modi possiamo apportare al cambiamento? L'ordine delle monete non ha importanza.

Ad esempio, per N = 4 e S = {1,2,3}, ci sono quattro soluzioni: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}. Quindi l'output dovrebbe essere 4. Per N = 10 e S = {2, 5, 3, 6}, ci sono cinque soluzioni: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} e {5,5}. Quindi l'uscita dovrebbe essere 5.

mi si avvicinò con la soluzione:

// recurrence relation 
count[N] = count[N-d] for all denomination <= N 

Source code 
----------- 

public static int numWays(int N, int[] denoms) { 
    if (N == 0) 
    return 0; 

    int[] ways = new int[N+1]; 
    ways[0] = 1; 

    for (int i=1; i<=N; i++) { 
    ways[i] = 0; 
    for (int d : denoms) { 
     if (d <= i) { 
      ways[i] += ways[i-d]; 
     } 
    } 
    } 

    return ways[N]; 
} 

Ma questo conta i duplicati che hanno le stesse denominazioni, ma in ordine diverso. Ad esempio, se denominazioni = {1,2} e N = 3, allora conta {1,1,1}, {2,1}, {1,2} che ha la voce duplicata {1,2}.

Vedo che la soluzione DP descritta nel collegamento here evita i duplicati. Capisco come funziona la relazione di ricorrenza e tutto, ma non sono in grado di capire come sia in grado di evitare i duplicati mentre la mia soluzione non lo è. Per favore, spiegami l'idea.

Answer 1

Lasciate C(i, j) il numero di modi per rendere il totale i utilizzando monete di denominazione S1, ..., Sj. Il tuo codice implementa la seguente ricorrenza (modi ordinati).

C(i, m) | i < 0 = 0 
     | i == 0 = 1 
     | i > 0 = sum_{j = 1}^m C(i - Sj, m) 

Il codice collegato implementa una ricorrenza diversa (modi non ordinati).

C(i, j) | i < 0   = 0 
     | i == 0   = 1 
     | i > 0 && j <= 0 = 0 
     | i > 0 && j > 0 = C(i - Sj, j) + C(i, j - 1) 

La differenza tra i due codici è sottile: più o meno quanto i loop sono annidati. Il tuo aggiunge tutti i termini per , ma il codice collegato aggiunge il termine j per ogni i, quindi il termine j + 1 per ogni i, ecc. Di conseguenza, quando il codice collegato considera la possibilità di utilizzare un denominazione- Sj moneta dal totale parziale i, implicitamente sta considerando solo quelle soluzioni che continuano con monete di denominazione S1, ..., Sj, perché il totale corrente per i - Sj non include le possibilità che utilizzano altre monete.