硬币兑换的空间优化解决方案

给定一个值 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。

我找到了3种方法HERE http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/。但无法理解仅使用一维数组 table[] 的空间优化动态编程方法。

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<m; i++)
        for(int j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]];

    return table[n];
}

首先注意table[i]是当N=i时硬币找零的方式数。

给定算法根据给定的一组硬币 (S[]) 填充此数组 (table[])。 最初，table[] 中的所有值都初始化为 0。并且 table[0] 设置为 0（这是基本情况 N=0）。

每个硬币按以下方式将表[]中的值相加。

对于价值 X 的硬币，以下是对表 [] 的更新 -

1. 表[X] = 表[X] + 1

   这很容易理解。具体来说，这会添加解决方案 {X}。

2. 对于所有 Y > X

   表[Y] = 表[Y] + 表[Y-X]

   这很难理解。以 X = 3 为例，并考虑 Y = 4 的情况。

   4 = 3 + 1 即 4 可以通过组合 3 和 1 得到。根据定义，得到 1 的方法有表[1]。因此表[4]中添加了许多方法。这就是为什么上面的表达式使用 table[Y-X]。

算法中的以下行代表相同的内容（以上两个步骤） -

table[j] += table[j-S[i]];  

在算法结束时，table[n] 包含 n 的解。