思路：本题是学习了完全背包问题之后的第一道应用题，从题目的意思中我们可以知道，能使用零钱的次数是无限的，也就是同一个数值的钱能被重复使用多次我们把目标金额看成背包的总容量，把单个零钱看成是重量和价值，那么本题完美符合完全背包的要求。
我们设dp数组，则dp[j]在题中表示组合成总金额j一共有多少中组合方法，组合问题的递推公式我们一般使用累加的方式 即dp[j] += dp[j-coins[i]]，因为假设如果包里已经有一个coins[i] 那么 有dp[j-coins[i]]种方法得到dp[j].
在进行遍历的时候，我们对于组合问题应当采取先遍历物品再遍历背包，因为组合问题并不在意物品的顺序，不管是【1，2，3】还是【3，2，1】都代表同一个组合，这样进行遍历不会出现代表同一个组合的重复的集合
class Solution {
public int change(int amount, int[] coins) {
// amount表示总金额 也就是背包的容量;
// coin 表示物品的重量和价值
// dp[j]表示组合成总金额j一共有多少中组合方法
int[] dp = new int[amount+1];
// 初始化 组成0只有一种方法就是每个都放0个
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];
}
}
思路：本题从完全背包组合问题变成了完全背包排列问题，我们在遍历的时候应该先遍历背包，再遍历物品，保证会出现元素相同顺序不同的组合
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 0; j <= target; j++){
for (int i = 0; i < nums.length; i++) {
if (j - nums[i] >= 0){
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
}
}
