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

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,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

我会尽力为别人解释的。。

考虑这段代码-

dp = [[0 for i in range(len(coins))] for j in range(n+1)]
for i in range(n+1):
    for j in range(len(coins)):
        if i == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i][j-1]

        if i - coins[j] >= 0:
            dp[i][j] += dp[i-coins[j]][j]

print dp[n][len(coins)-1]

这种方法相当基本，没有空间优化。起初，我们可能认为我们只是从列索引j-1中访问信息，因此我们可以删除列，但事实并非如此，因为我们也在访问dp[i-coins[j]][j]。因此j'th索引中包含的信息非常有用，我们不能删除这些列。

现在想想看，

dp = [[0 for i in range(n+1)] for j in range(len(coins))]
for i in range(len(coins)):
    for j in range(n+1):
        if j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j]

        if j - coins[i] >= 0:
            dp[i][j] += dp[i][j-coins[i]]

print dp[len(coins)-1][n]

我们所做的一切都是颠倒for循环的顺序。仔细观察，我们可以看到dp[i][j-硬币[i]]与dp[i][j]来自同一行。这是否意味着我们不需要维护来自其他行的信息？是的，我们没有。

现在有两种方法可以做到这一点，或者维护两个数组，一个用于dp[i]，另一个用于dp[i-1]，或者完全删除行索引，这将导致在dp[j]处为i的所有值积累所有数据。

第二种方法的代码-

dp = [0 for i in range(n+1)]

dp[0] = 1
for i in range(len(coins)):
    for j in range(coins[i], n+1):
        dp[j] += dp[j-coins[i]]

return dp[n]

Answer 2

试着用这种方法来理解算法。

表[i][j]意味着使用第一种i类型的硬币来改变j的价值。然后：

表[i][j]=表[i-1][j]表[i][j-S[i]]

显然，在制作j硬币时，你有两种选择。不使用第i个硬币或第i个硬币。不使用第i枚硬币时，解决方案编号为表[i-1][j]。使用第i枚硬币时，解决方案编号为表[i][j-S[i]]，这意味着使用前i枚硬币组成j-S[i]值。因此，总数是两者的总和，即表[i-1][j]表[i][j-S[i]]

在代码中，您将看到for循环。外循环迭代i，内循环迭代j。=语句根据上述等式计算表[i][j]。

编辑

table[j]在您的代码中实际上是table[i][j]我在上面所说的，i是您循环中的值。循环后table[N]表示table[M][N]，表示使用第一个M硬币，即所有硬币，为N创造价值。

我将根据代码提供更多细节：

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

当i=0时，表[j]意味着使用前1个硬币来更改j的值。例如，table[2]现在意味着使用coins{1}为2进行更改。因此：

table[1] = table[1] + table[1 - S[0]] = table[1] + table[0] = 1 + 0= 1
table[2] = table[2] + table[2 - S[0]] = table[2] + table[1] = 0 + 1= 1
table[3] = 1
table[4] = 1

table[1]~table[4]现在意味着使用硬币{1}分别对值1,2,3,4进行更改。

当i=1时，table[j]意味着使用coin{1,2}对值j进行更改。

table[2] = table[2] + table[2 - S[1]] = table[2] + table[0] = 1 + 1= 2
table[3] = table[3] + table[3 - S[1]] = 1 + 1 = 2
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3

下面的过程是相同的。

最后，当i=1时，我们取出表[4]，并对其进行分析：

table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3

这里左边的表[4]是我们正在计算的值，实际上是表[i=1][4]<右侧的代码>表[4]表示上一个值，在本例中，表[i=0][4]。它可以扩展到：

table[i=1][4] = table[i=0][4] + table[i=1][4 - S[1]]

方程式正是

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

编辑后续问题

如果你认为你真的理解这个问题，试着用一个新的约束来解决同样的问题。如果每枚硬币只能使用一次怎么办？例如，N=4和S={1,2,3}，只有一个解{1,3}，所以输出应该是1。对于N=10和S={2,5,3,6}，仍然只有一个解{2,3,5}，输出为1。

提示：仅对原始代码进行一行更改就足够了。

答：http://ideone.com/t1JnEz

Answer 3

首先要注意的是，表[i]是N=i时硬币兑换的方式数。

给定算法填充这个数组（表[]）每个给定的硬币集（S[]）。最初，表[]中的所有值都初始化为0。表[0]设置为0（这是基本情况N=0）。

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

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

>

table[X]=table[X] 1

这很容易理解。特别是，这增加了解决方案{X}。

无论如何

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

这很难理解。以x＝3为例，考虑y＝4的情况。

4=3 1，即通过组合3和1可获得4。根据定义，得到1的方法有很多，如表[1]。因此，表[4]中增加了许多方法。这就是上面的表达式使用表[Y-X]的原因。

算法中的下一行表示相同的（以上两个步骤）-

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

在算法的末尾，表[n]包含n的解。