空间优化的硬币变化解决方案

Question

给定值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种方法.但是无法理解空间优化的动态编程方法,其中仅使用单维数组表[].

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

Answer 1

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

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

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

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

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

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

2. 对于所有 Y > X

   表[Y] = 表[Y] + 表[YX]

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

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

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

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

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