思路：本題是學(xué)習(xí)了完全背包問題之后的第一道應(yīng)用題，從題目的意思中我們可以知道，能使用零錢的次數(shù)是無限的，也就是同一個(gè)數(shù)值的錢能被重復(fù)使用多次我們把目標(biāo)金額看成背包的總?cè)萘浚褑蝹€(gè)零錢看成是重量和價(jià)值，那么本題完美符合完全背包的要求。
我們?cè)O(shè)dp數(shù)組，則dp[j]在題中表示組合成總金額j一共有多少中組合方法，組合問題的遞推公式我們一般使用累加的方式 即dp[j] += dp[j-coins[i]]，因?yàn)榧僭O(shè)如果包里已經(jīng)有一個(gè)coins[i] 那么 有dp[j-coins[i]]種方法得到dp[j].
在進(jìn)行遍歷的時(shí)候，我們對(duì)于組合問題應(yīng)當(dāng)采取先遍歷物品再遍歷背包，因?yàn)榻M合問題并不在意物品的順序，不管是【1，2，3】還是【3，2，1】都代表同一個(gè)組合，這樣進(jìn)行遍歷不會(huì)出現(xiàn)代表同一個(gè)組合的重復(fù)的集合

class Solution {
    public int change(int amount, int[] coins) {
//        amount表示總金額 也就是背包的容量;
//        coin 表示物品的重量和價(jià)值
//        dp[j]表示組合成總金額j一共有多少中組合方法
        int[] dp = new int[amount+1];
//        初始化 組成0只有一種方法就是每個(gè)都放0個(gè)
        dp[0] = 1;
        for (int i = 0 ; i < coins.length;i++){
//            完全背包問題 可重復(fù)放
            for (int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];

    }
}

思路：本題從完全背包組合問題變成了完全背包排列問題，我們?cè)诒闅v的時(shí)候應(yīng)該先遍歷背包，再遍歷物品，保證會(huì)出現(xiàn)元素相同順序不同的組合

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];


    }
}