我一直在寻找一个很好的解决了更改决策的问题 ，我发现这个代码（蟒蛇）：
target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
for i in range(coin,target+1):
ways[i]+=ways[i-coin]
print(ways[target])
我的理解没有问题了代码字面上做，但我不明白为什么它的工作原理。 任何人都可以帮助吗？
要获得所有可能的集合的元素等于“A”或“B”或“C”（我们的硬币），总计为“X”，您可以：
因此，许多方式可以得到X为的方法可以得到Xa和Xb及Xc数之和。
ways[i]+=ways[i-coin]
剩下的就是简单的复发。
额外提示：在开始时，你可以在只有一个碍事设定总和为零（空集）
ways = [1]+[0]*target
这是一个经典的例子动态规划 。 它采用高速缓存以避免计数之类的东西3 + 2 = 5两次（因为另一个可能的解决方案：2 + 3）的陷阱。 递归算法属于这一陷阱。 让我们专注于一个简单的例子，其中target = 5和coins = [1,2,3] 这件作品的代码，你贴数：
而递归版本数：
递归代码：
coinsOptions = [1, 2, 3]
def numberOfWays(target):
if (target < 0):
return 0
elif(target == 0):
return 1
else:
return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)
动态规划：
target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
for i in range(coin, target+1):
ways[i]+=ways[i-coin]
print ways[target]
代码背后的主要思想是：“在每一个步骤有ways的方法，使改变i的金额给硬币[1,...coin] ”。
因此，在第一次迭代你只有与面额硬币1 。 我相信这是明显地看到，只有一个给只有这些硬币的任何目标的改变方式。 在这一步ways排列的样子[1,...1]只有一个从所有目标的方法0到target ）。
在下一步，我们添加一个硬币的面额2到以前的钱币。 现在，我们可以计算出有多少变化组合有从每个目标0至target 。 显然，组合的数量将增加只对目标> = 2 （或新的硬币加入，在一般情况下）。 因此，对于一个目标等于2的组合的数量会ways[2](old) + ways[0](new) 。 一般来说，每次当时间i等于新币介绍我们需要增加1到以前的号码组合，其中新组合将只从一个硬币包括。
对于target > 2 ，答案将包括“的所有组合的总和的target具有量小于所有硬币coin ”和“的所有组合coin量具有小于所有硬币coin本身”。
在这里，我描述了两个基本步骤，但我希望它是易于推广它。
让我告诉你一个计算树target = 4和coins=[1,2]
方法[4]中给出的硬币= [1,2] =
方法[4]中给出硬币= [1] +方法[2]给出的硬币= [1,2] =
1种+方式[2]给出的硬币= [1] +方法[0]给定硬币= [1,2] =
1 + 1 + 1 = 3
因此，有三种方式给一个变化： [1,1,1,1], [1,1,2], [2,2]
上面给出的代码是完全等效于递归溶液。 如果你理解了递归解决方案 ，我敢打赌，你明白上面给出的解决方案。
您发布的解决方案总结这段代码的版本。
/// <summary>
/// We are going to fill the biggest coins one by one.
/// </summary>
/// <param name="n"> the amount of money </param>
public static void MakeChange (int n)
{
int n1, n2, n3; // residual of amount after each coin
int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c
for (quarter = n/25; quarter >= 0; quarter--)
{
n1 = n - 25 * quarter;
for (dime = n1/10; dime >= 0; dime--)
{
n2 = n1 - 10 * dime;
for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--)
{
n3 = n2 - 5 * nickel;
Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent.
}
}
}
}
