此题很容易想到DP的解法，但是非常容易出错。
用dp[i]表示总数额为i的硬币组合数目。那么显然有动态转移方程:
for (j=0; j<coins.size(); j++)
dp[i] += dp[i-coins[j]]那么对于i=0~amount的循环应该放在哪里呢？这样的框架是错误的：
for (int i=0; i<=amount; i++)
for (j=0; j<coins.size(); j++)
dp[i] += dp[i-coins[j]];举个例子：总数额为3时，1+2 和 2+1 的两种方法就会重复计算。所以我们必须把两个外循环的框架反过来：
for (j=0; j<coins.size(); j++)
for (int i=0; i<=amount; i++)
dp[i] += dp[i-coins[j]];这样，我们保证了最后一步总是加入coins[j]，这样得到的dp[i]对应的所有方案都不会是重复的（对于使用coins[0]~coins[j]而言）。
此题本质上可以归类为背包问题。背包问题的套路是：最外层循环是物品的种类i，内层的循环是背包的容量c。状态变量dp[c]表示（当前物品种类的条件下）容量c最多能装的物品件数。
对于物品i我们看做是第一次出现，我们会考虑是否加入该物品（或者根据题意考虑加入多少该物品）会对于dp[c]的影响。显然，我们可以遍历物品i是否使用（或者使用多少）。在本题中，不取的话dp[c]不变，取一个的话有dp[c] = dp[c-coin[i]]+1，取两个的话有dp[c] = dp[c-2*coin[i]]+2...直至物品i放不下位置，取上述最大的dp[c]。
当然以上的做法虽然严格按照了背包问题的模板，但是需要三层循环，效率不高。不过我们可以把内部的两层循环稍微变形，从而就等价于前面写的代码。这是因为我们在从小到大遍历c的时候，所能盛装物品i的件数也是同步增长的：更新了小的dp[c]，马上就能用来更新较大的dp[c]。