Số cách để thực hiện thay đổi đối với số tiền N

Question

Tôi đã xem qua vấn đề này:

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

Cho một giá trị N, nếu chúng ta muốn thực hiện thay đổi cho N cent, và chúng tôi có cung cấp vô hạn của mỗi đồng tiền có giá trị S = {S1, S2, .., Sm}, chúng ta có thể thay đổi bao nhiêu cách? Thứ tự của tiền xu không quan trọng. Ví dụ: đối với N = 4 và S = {1,2,3}, có bốn giải pháp: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}. Vì vậy, đầu ra phải là 4. Đối với N = 10 và S = {2, 5, 3, 6}, có năm giải pháp: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} và {5,5}. Vì vậy, sản lượng nên được 5.

tôi đã đưa ra các giải pháp:

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

Nhưng điều này đếm các bản sao mà có mệnh giá tương tự nhưng theo thứ tự khác nhau. Ví dụ, nếu mệnh giá = {1,2} và N = 3, thì nó tính {1,1,1}, {2,1}, {1,2} có mục trùng lặp {1,2}.

Tôi thấy rằng giải pháp DP được mô tả trong liên kết here tránh trùng lặp. Tôi hiểu làm thế nào các mối quan hệ lặp lại hoạt động và tất cả nhưng tôi không thể hiểu làm thế nào nó có thể tránh các bản sao trong khi giải pháp của tôi là không. Xin giải thích ý tưởng đằng sau.

Answer 1

Hãy để C(i, j) số cách để thực hiện tổng số i sử dụng đồng tiền mệnh giá S1, ..., Sj. Mã của bạn thực hiện các lần lặp lại sau đây (các cách đặt hàng).

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

Mã được liên kết thực hiện sự lặp lại khác nhau (cách không theo thứ tự).

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) 

Sự khác biệt giữa hai mã là tinh tế: nhiều hay ít chỉ là cách vòng được lồng nhau. Bạn thêm tất cả các điều khoản cho i trước khi chuyển sang i + 1, nhưng mã được liên kết thêm cụm từ j cho mỗi i, sau đó là cụm từ j + 1 cho mỗi i, v.v. Kết quả là khi mã được liên kết xem xét khả năng sử dụng mệnh giá - Sj đồng xu từ tổng phụ i, nó ngầm chỉ xem xét những giải pháp tiếp tục với đồng tiền mệnh giá S1, ..., Sj, vì tổng số hiện tại cho i - Sj không bao gồm các khả năng sử dụng đồng tiền khác.