ilość sposobów, aby zmiany na kwotę N

Question

natknąłem tego problemu:

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

Biorąc pod uwagę wartość N, jeśli chcemy, aby zmiany do N centów, a mamy nieskończoną dostaw każda z monet o wartości S = {S1, S2, .., Sm}, ile sposobów możemy dokonać zmiany? Kolejność monet nie ma znaczenia.

Na przykład dla N = 4 i S = {1,2,3} istnieją cztery rozwiązania: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}. Zatem wynik powinien wynosić 4. Dla N = 10 i S = {2, 5, 3, 6}, istnieje pięć rozwiązań: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} i {5,5}. Więc wyjście powinno być 5.

wymyśliłem rozwiązanie:

// 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]; 
} 

Ale liczy duplikaty, które mają te same nominały, ale w innej kolejności. Na przykład, jeśli nominały = {1,2} i N = 3, to liczy {1,1,1}, {2,1}, {1,2}, które mają zduplikowane wejście {1,2}.

Widzę, że rozwiązanie DP opisane w łączu here pozwala uniknąć duplikatów. Rozumiem, jak działa relacja nawrotów, ale nie jestem w stanie zrozumieć, w jaki sposób można uniknąć duplikatów, podczas gdy moje rozwiązanie nie jest możliwe. Proszę wyjaśnij tę ideę.

Answer 1

Pozwolić C(i, j) liczbę sposobów, aby całkowita liczba i przy użyciu monet o nominałach S1, ..., Sj. Twój kod implementuje następującą rekurencję (uporządkowane sposoby).

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

Połączony kod implementuje inną rekurencję (sposoby nieuporządkowane).

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) 

Różnica między tymi dwoma kodami jest subtelna: mniej więcej po prostu, jak pętle są zagnieżdżane. Dodaje wszystkie warunki dla i przed przejściem do i + 1, ale połączony kod dodaje termin j dla każdego i, następnie j + 1 dla każdego i itd. W rezultacie, gdy połączony kod rozważa możliwość użycia denominacja - Sj moneta z sumy częściowej i, domyślnie rozważa tylko te rozwiązania, które są kontynuowane monetami o nominałach S1, ..., Sj, ponieważ obecna suma dla i - Sj nie obejmuje możliwości, które wykorzystują inne monety.