首页 1 2 3 4 5 6 7

找零钱-动态规划

问题：

假设有m种面值不同的硬币，个个面值存于数组S ={S1，S2，… Sm}中，现在用这些硬币来找钱，各种硬币的使用个数不限。求对于给定的钱数N，我们最多有几种不同的找钱方式。硬币的顺序并不重要。

例如，对于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）解决方案包含至少一个第m种硬币。
让数（S [] , M, N）是该函数来计算解的数目，则它可以表示为计数的总和（S [], M-1, N）和计数（S []，M，N-Sm）。
因此，这个问题具有最优子结构性质的问题。

2) 重叠子问题
下面是一个简单的递归实现硬币找零问题。遵循上面提到的递归结构。

#include<stdio.h>
int count( int S[], int m, int n )
{
    // 如果n为0，就找到了一个方案
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    // 没有硬币可用了，也返回0
    if (m <=0 )
        return 0;
    // 按照上面的递归函数
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

// 测试
int 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)
                                               /  \
                                              /    \  
                                             .      .

所以，硬币找零问题具有符合动态规划的两个重要属性。像其他典型的动态规划（DP）的问题，可通过自下而上的方式打表，存储相同的子问题。当然上面的递归程序也可以改写成记忆化存储的方式来提高效率。
下面是动态规划的程序：

#include<stdio.h>

int count( int S[], int m, int n )
{
    int i, j, x, y;

    // 通过自下而上的方式打表我们需要n+1行
    // 最基本的情况是n=0
    int table[n+1][m];

    // 初始化n=0的情况 (参考上面的递归程序)
    for (i=0; i<m; i++)
        table[0][i] = 1;

    for (i = 1; i < n+1; i++)
    {
        for (j = 0; j < m; j++)
        {
            // 包括 S[j] 的方案数
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

            // 不包括 S[j] 的方案数
            y = (j >= 1)? table[i][j-1]: 0;

            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}

// 测试
int main()
{
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf(" %d ", count(arr, m, n));
    return 0;
}

时间复杂度：O(mn)

以下为上面程序的优化版本。这里所需要的辅助空间为O(n)。因为我们在打表时，本行只和上一行有关，类似01背包问题。

int count( int S[], int m, int n )
{
    int table[n+1];
    memset(table, 0, sizeof(table));
    //初始化基本情况
    table[0] = 1;

    for(int i=0; i<m; i++)
        for(int j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]];

    return table[n];
}