Количество способов сделать изменения для количества N

Question

Я наткнулся на эту проблему:

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

Учитывая значение N, если мы хотим внести изменения в N центов, и у нас есть бесконечный запас каждая из S = {S1, S2, .., Sm} ценных монет, сколько способов мы можем внести изменения? Порядок монет не имеет значения.

Например, для N = 4 и S = ​​{1,2,3} существует четыре решения: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}. Таким образом, выход должен быть 4. Для N = 10 и S = ​​{2, 5, 3, 6} существует пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Таким образом, выход должен быть 5.

Я придумал решение:

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

Но это считается дубликатами, которые имеют те же номиналы, но в другом порядке. Например, если деноминации = {1,2} и N = 3, то он подсчитывает {1,1,1}, {2,1}, {1,2}, который имеет двойную запись {1,2}.

Я вижу, что решение DP, описанное в ссылке here, позволяет избежать дублирования. Я понимаю, как работает рекуррентное отношение и все, но я не могу понять, как он может избежать дубликатов, пока мое решение не является. Пожалуйста, объясните идею.

Answer 1

Позвольте C(i, j) количество способов сделать i используя монеты достоинством S1, ..., Sj. В вашем коде реализовано следующее повторение (упорядоченные способы).

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

Связанный код реализует различные повторения (неупорядоченные способы).

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) 

Разница между двумя кодами тонкая: более или менее то, как петли вложены. Вы добавили все условия для i, прежде чем переходить к i + 1, но связанный код добавляет j срок для каждого i, а затем j + 1 срок для каждого i и т. Д. В результате, когда связанный код рассматривает возможность использования деноминация - Sj монета из промежуточного итога i, она неявно рассматривает только те решения, которые продолжаются с монетами номиналов S1, ..., Sj, так как текущая сумма для i - Sj не включает возможности, которые используют другие монеты.