space 找币优化方案
space optimized solution for coin change
给定一个值 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。但无法理解仅使用一维数组 table[] 的 space 优化动态规划方法。
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][j]表示使用前i种币找零价值j。然后：
table[i][j] = table[i-1][j] + table[i][j-S[i]]
很明显，在制作j个硬币时，你有两种选择。不使用第 i 个硬币或使用第 i 个硬币。不使用第i个硬币时，解数为table[i-1][j]。当使用第i个硬币时，解数为table[i][j-S[i]]，即用前i个硬币组成j-S[i] value.Therefore，总和为两者之和，即table[i-1][j] + table[i][j-S[i]]
在代码中，您将看到 for 循环。外循环遍历 i，内循环遍历 j。 += 语句根据上面的等式计算 table[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时，table[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
之后，我们在i = 0时得到了结果。table[1] ~ table[4]现在意味着使用coin {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
后面的过程同上。
最后，我们把table[4]当i = 1拿出来分析一下：
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3
这里左边的table[4]是我们计算的值，实际上是table[i=1][4]。右侧的 table[4] 代表之前的值，在本例中为 table[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.
提示：原代码只需改动一行即可。
首先注意table[i]是N=i时找零的次数
给定算法根据给定的一组硬币 (S[]) 填充此数组 (table[])。
最初 table[] 中的所有值都初始化为 0。并且 table[0] 设置为 0（这是基本情况 N=0）。
每个硬币按以下方式将 table[] 中的值相加。
对于价值 X 的硬币，以下是 table[] -
的更新
table[X] = table[X] + 1
这个很容易理解。具体来说，这会添加解决方案 {X}.
对于所有 Y > X
table[Y] = table[Y] + table[Y-X]
这很难理解。以 X = 3 为例，并考虑 Y = 4 的情况。
4 = 3 + 1 即 4 可以通过组合 3 和 1 得到。根据定义，得到 1 的方法数是 table[1]。所以很多方法都加到table[4]。这就是为什么上面的表达式使用 table[Y-X].
算法中的下一行表示相同（以上两个步骤）-
table[j] += table[j-S[i]];
在算法结束时，table[n] 包含 n 的解。
会尝试为其他人解释..
考虑这段代码 -
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]
这种方法相当基础，没有 space 优化。起初我们可能认为我们只是从列索引 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-coins[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]
给定一个值 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。但无法理解仅使用一维数组 table[] 的 space 优化动态规划方法。
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][j]表示使用前i种币找零价值j。然后：
table[i][j] = table[i-1][j] + table[i][j-S[i]]
很明显，在制作j个硬币时，你有两种选择。不使用第 i 个硬币或使用第 i 个硬币。不使用第i个硬币时，解数为table[i-1][j]。当使用第i个硬币时，解数为table[i][j-S[i]]，即用前i个硬币组成j-S[i] value.Therefore，总和为两者之和，即table[i-1][j] + table[i][j-S[i]]
在代码中，您将看到 for 循环。外循环遍历 i，内循环遍历 j。 += 语句根据上面的等式计算 table[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时，table[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
之后，我们在i = 0时得到了结果。table[1] ~ table[4]现在意味着使用coin {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
后面的过程同上。
最后，我们把table[4]当i = 1拿出来分析一下：
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3
这里左边的table[4]是我们计算的值，实际上是table[i=1][4]。右侧的 table[4] 代表之前的值，在本例中为 table[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.
提示：原代码只需改动一行即可。
首先注意table[i]是N=i时找零的次数
给定算法根据给定的一组硬币 (S[]) 填充此数组 (table[])。 最初 table[] 中的所有值都初始化为 0。并且 table[0] 设置为 0（这是基本情况 N=0）。
每个硬币按以下方式将 table[] 中的值相加。
对于价值 X 的硬币，以下是 table[] -
的更新table[X] = table[X] + 1
这个很容易理解。具体来说，这会添加解决方案 {X}.
对于所有 Y > X
table[Y] = table[Y] + table[Y-X]
这很难理解。以 X = 3 为例，并考虑 Y = 4 的情况。
4 = 3 + 1 即 4 可以通过组合 3 和 1 得到。根据定义，得到 1 的方法数是 table[1]。所以很多方法都加到table[4]。这就是为什么上面的表达式使用 table[Y-X].
算法中的下一行表示相同（以上两个步骤）-
table[j] += table[j-S[i]];
在算法结束时，table[n] 包含 n 的解。
会尝试为其他人解释..
考虑这段代码 -
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]
这种方法相当基础，没有 space 优化。起初我们可能认为我们只是从列索引 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-coins[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]