原题链接：. - 力扣（LeetCode）
给你一个整数数组 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
思路：
本题是完全背包问题，即 数字可以无限次装入背包，求背包的最大价值的问题。本题是求装满背包有多少种方法。采用动态规划解决。dp[ j ] ：要装满容量为 j 的背包有 dp[ j ] 种方法。
递推公式：要装满容量为 j 的背包有哪些来源呢？如果 容量为 j 的背包装入了 大小为 coins[ i ] 的物品，那么就变成了一个 容量为 j - coins[ i ] 的背包，那么 dp[ j ] 就应该加上 dp[ j - coins[ i ]] 。故 dp[ j ] += dp[ j - coins[ i ] ] （求装满背包有几种方法，基本都是这个递推公式）
初始化：将 dp[ 0 ] 初始化为 1，其余 dp 值初始化为 0。遍历顺序：先遍历数字再遍历背包容量。如果是先遍历物品（数字）再遍历背包容量的话，就是求装满背包的组合数。如果是先遍历背包容量再遍历物品（数字）的话，就是求装满背包的排列数。由于是完全背包，可以重复放入，所以背包容量可以由小到大遍历。
代码：
class Solution {
public int change(int amount, int[] coins) {
//dp[j]表示装满容量为j的背包有多少种组合
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}参考：代码随想录
