本文共 3648 字，大约阅读时间需要 12 分钟。

原文地址：

已知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。

1）最优的子结构

想得到答案的总数，我们可以将所有的方法分成两部分。 1）方案中不包含第m种硬币（或者Sm） 2）方案中至少包含一个Sm 设count(S[], m, n) 是解决方案的总数，那么它可以写为count(S[], m-1, n)与count(S[], m, n-Sm)的和。 所以这个问题具有最优子结构属性，可以通过解决子问题来解决。

2）重复的子问题

下面是硬币兑换问题的一个简单递归实现，这个实现是根据上述的递归结构来写的。

#include
   
    // Returns the count of ways we can sum  S[0...m-1] coins to get sum nint count( int S[], int m, int n ){    // If n is 0 then there is 1 solution (do not include any coin)    if (n == 0)        return 1;    // If n is less than 0 then no solution exists    if (n < 0)        return 0;    // If there are no coins and n is greater than 0, then no solution exist    if (m <=0 && n >= 1)        return 0;    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );}// Driver program to test above functionint main(){    int i, j;    int arr[] = {
  1, 2, 3};    int m = sizeof(arr)/sizeof(arr[0]);    printf("%d ", count(arr, m, 4));    getchar();    return 0;}
   

你应该能发现有的子问题已经被重复计算了，请看下面S = {1, 2, 3}，n = 5的递归树。

C({1}, 3)被调用了两次，如果我们把树完全画出来，那么我们可以看到有许多子问题都重复计算了。

C() --> count()                              C({1,2,3}, 5)                                                /                \                         /                   \                           C({1,2,3}, 2)                 C({1,2}, 5)            /     \                        /         \           /        \                     /           \   C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)           /         \                /    \           /   \          /           \              /      \         /     \    C({1,2},0)  C({1},2)        C({1,2},1) C({1},3)C({1}, 4)  C({}, 5)                   / \             / \       / \        /  \                      /   \           /   \     /   \      /    \                 .      .         .     .   .     . C({1}, 3) C({}, 4)                                               /  \                                              /    \                                               .      .

因为相同的问题又被调用了，这个问题有重复子问题属性，所以这个硬币兑换问题同时具有动态规划问题的两个属性。就像其他典型的动态规划问题一样，可以通过自底向上地建立一个临时数组table[][]来避免子问题的重复计算。

动态规划问题答案

#include
   
    int count( int S[], int m, int n ){    int i, j, x, y;    // We need n+1 rows as the table is consturcted in bottom up manner using     // the base case 0 value case (n = 0)    int table[n+1][m];    // Fill the enteries for 0 value case (n = 0)    for (i=0; i
    
     = 0)? table[i - S[j]][j]: 0;            // Count of solutions excluding S[j]            y = (j >= 1)? table[i][j-1]: 0;            // total count            table[i][j] = x + y;        }    }    return table[n][m-1];}// Driver program to test above functionint main(){    int arr[] = {
  1, 2, 3};    int m = sizeof(arr)/sizeof(arr[0]);    int n = 4;    printf(" %d ", count(arr, m, n));    return 0;}
    
   

输出：

4

时间复杂度：O(mn)

下面是方法2的简单版本，只需要O(n)的附件空间。

int count( int S[], int m, int n ){    // table[i] will be storing the number of solutions for    // value i. We need n+1 rows as the table is consturcted    // in bottom up manner using the base case (n = 0)    int table[n+1];    // Initialize all table values as 0    memset(table, 0, sizeof(table));    // Base case (If given value is 0)    table[0] = 1;    // Pick all coins one by one and update the table[] values    // after the index greater than or equal to the value of the    // picked coin    for(int i=0; i

参考文献：

转载地址：http://lgqii.baihongyu.com/