给定不同面值的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
参考：https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/
此题类似于爬楼梯问题。
对于爬楼梯问题，dp[i] = dp[i - 1] + dp[i - 2]如果我们把问题泛化，不再是固定的 1， 2，而是任意给定台阶数，例如，1，2，5呢？我们只需要修改我们的dp方程为 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 5]，也就是 dp[i] = dp[i] + dp[i - j]，j = 1，2，5。(此处状态转移方程的推导需要参考完全背包状态转移方程的推导)。而对于此题，我们定义子问题：problem(i) = sum(problem(i - j))，j = 1，2，5. 含义为凑成总金额 i 的硬币组合数等于凑成总金额硬币 i - 1，i - 2， i - 5，…的子问题之和。 然后我们发现这个子问题与上面泛化的爬楼梯问题居然是一样的，那后面的状态数组和状态转移方程也是一样的，那么代码也应该差不多，代码如下： 但是当运行上面的代码之和，会发现这个代码并不正确，得到的结果比预期的大。究其原因，该代码计算的结果是排列数，而不是组合数；而更根本的原因是我们子问题的定义出了错误。
正确的子问题定义应该是，problem(k, i) = problem(k- 1, i) + problem(k, i - k);即前 k 个硬币凑齐金额 i 的组合数 = 前 k - 1 个硬币凑齐金额 i 的组合数 + 在原来 i - coins[k - 1](第 k 个硬币的下标为 k - 1) 的基础上使用硬币的组合数。说的更加直白一点，那就是用前 k 个硬币凑齐金额 i，要分两种情况考虑：一种是只用前 k - 1 个硬币就凑齐了；一种是前面已经凑到了 i - coins[k - 1]，现在就差第 k 个硬币了。状态数组就是 dp[k][i]，即前 k 个硬币凑齐金额 i 的组合数。 二维数组的第一个维度用于记录当前组合有没有用到硬币 k。第二个维度记录现在凑的金额是多少？如果没有第一个维度信息，当我们凑到金额 i 的时候，我们不知道之前有没有用到硬币 k。因为这是个组合问题，我们不关心硬币的使用顺序，而是关心硬币有没有被使用到。 是否使用第 k 个硬币受到之前情况的影响。 状态转移方程如下： if 金额数大于硬币 dp[k][i] = dp[k - 1][i] + dp[k][i - coins[k - 1]]; else dp[k][i] = dp[k - 1][i];代码 此代码交换里面的循环不会应该最终的结果。
重新定义子问题：对于硬币从 0 到 k，必须使用第 k 个硬币时，当前金额的组合数。
参考：https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/
举例：amount = 11，可用硬币面值有 2 美分，5 美分和 10 美分。然后硬币的数量是无限的。 基本情况：没有硬币或总金额为 0
如果总金额为 0，那么只有一种组合情况：0另一个基本情况是：没有硬币，若 amount > 0 ，则组合数为 0；若 amount == 0，则组合数为 1。进一步情况：2美分
很明显，这里可能会有 1 种 或 0 种组合。偶数金额为 1 种，奇数金额为 0 种。首先，所有小于 2 美分的金额不会首受到 2 美分硬币的影响。因此对于amount = 0 和 amount = 1的结果没有变化。从 amount = 2 开始，可以使用 2 美分硬币进行组合。我们使用 2 美分硬币来组合 amount = 2，则金额 2 美分的组合数等于 amount = 0 的组合数量，即 1. 同理，amount = 3 的组合数量等于 amount = 1 的组合数，即 0. 我们可以推导出 dp 公式为：amount = x；dp[x] = dp[x] + dp[x - coin]，其中 coin = 2 美分，是当前添加的硬币的价值。更进一步：2 美分 + 5 美分 + 10 美分
先增加 5 美分的情况，公式是一样的；对于10美分也是一样的策略为：
从基本情况没有硬币开始，———添加硬币。对于每个添加的硬币,我们从金额 0 到 amount递归的计算组合数量。算法：
以基本情况没有硬币开始组合数量。dp[0] = 1，然后其余为 0.遍历所有硬币的面值： 对于每一个硬币，我们从金额 0 遍历到 amount 对于每一个 x，计算组合数：dp[x] += dp[x - coin] 返回 dp[amount]。时间复杂度： O(N * amount)，N为coins数组的长度 空间复杂度： O(amount)，dp数组使用的空间。
注意： 此时内外循环的顺序不可更改。
因为我们这里定义的子问题是：必须选择第 k 个硬币时，凑成金额 i 的方案。如果交换了，子问题就变成了：对于金额 i，我们选择硬币的方案。