刷题使我快乐，满脸开心.jpg
- 来源：力扣（LeetCode）
- 链接：https://leetcode.cn/problems/coin-change-ii/
- 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值互不相同0 <= amount <= 5000
思路
跟上台阶一样经典的动规题目，没啥好说的
不过这里有一个点需要说下，就是 硬币 和 金额谁在外层的问题，具体解释可以看代码注释。对应的问题概括下就是
动态规划的思路，要保证在前的操作不能对在后的操作产生影响，即
无后效性
没啥别的要说的，上代码，细节在注释~
代码
func change(amount int, coins []int) int {
dp := make([]int, amount+1)
// 对应一个都不选，只有这一种情况
dp[0] = 1
// coins遍历在内层，则会有重复情况导致结果出问题
// 比如以示例1做解释
// 金额3，只能由 1+1+1 或者 1+2 产生
// 金额2，只能由 1+1 或者 2 产生
// 但如果金额在外层循环，coins在内层
// 金额3，会是 dp[3] += dp[2] && dp[3] += dp[1]
// 这里的 dp[2] 里和 dp[1] 里其实存在了重复的 1+2 的情况
//for i := 1; i <= amount; i++ {
// for j := range coins {
// if i-coins[j] >= 0 {
// dp[i] += dp[i-coins[j]]
// }
// }
//}
// coins遍历在外层，则不会有重复情况
for i := range coins {
for j := coins[i]; j <= amount; j++ {
dp[j] += dp[j-coins[i]]
}
}
return dp[amount]
}