空间优化的硬币找零解决方案 [英] space optimized solution for coin change

问题描述

给定一个值N，如果我们要N分钱找零，并且我们有无限数量的S = {S1，S2，..，Sm}个有价硬币，我们可以用几种方法进行找零？硬币的顺序无关紧要。

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

例如，对于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。

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

我发现了3种方法这里。但是无法理解仅使用一维数组表[]的空间优化动态规划方法。

I found the 3 approaches HERE. But not able to understand the space optimized dynamic programming approach where only a single dimensional array table[] is used.

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

推荐答案

该表的首注[i ]是N = i时硬币更换的方式。

First note that table[i] is number of ways for coin change when N=i.

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

Given Algorithm fills this array (table[]) as per given set of coin (S[]). Initially all values in table[] are initialized to 0. And table[0] set to 0 (this is base case N=0).

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

Each coin adds up values in table[] in following manner.

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

For coin of value X, following are updates to table[] -

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

1. table[X] = table[X] + 1

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

This is easy to understand. Specifically this adds solution {X}.

Y> X的所有对象

for all Y > X

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

table[Y] = table[Y] + table[Y-X]

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

This is tricky to understand. Take example X = 3, and consider case for Y = 4.

4 = 3 +1，即4可通过将3和1相结合而获得，并通过table [1]是获得1的方法。因此，表[4]中添加了许多方法。这就是为什么上面的表达式使用table [YX]的原因。

4 = 3 + 1 i.e. 4 can be obtained by combining 3 and 1. And by definition number of ways to get 1 are table[1]. So that many ways are added to table[4]. Thats why above expression uses table[Y-X].

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

Following line in your algorithm represents the same (above two steps) -

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

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

At the end of algorithm, table[n] contains solution for n.

这篇关于空间优化的硬币找零解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！