Leetcode 518. 零錢兌換 II

題目鏈接: 零錢兌換 II
自己的思路:想不到，忘記這個遞推公式了！！！而且初始化也要值得注意！

正確思路:由于這個題每個數可以取多次，那么說明這是一個完全背包問題，而且背包的容量就是amount，所以這個題就是在問有多少種組合可以把背包裝滿；直接動規五部曲：1、dp數組的含義：從題目的目的出發，這道題是求組合數，所以dp[j]就表示背包容量為j的時候的組合數；2、遞推公式：這道題和前面零錢兌換的題一樣，都是求組合數，可以直接使用前面的求組合數的遞推公式，也就是dp[j]+=dp[j-coins[i]]，因為當我們固定一個的數的時候，組合的情況是把其他數所有的情況加起來！3、dp數組的初始化：這道題要把dp[0]初始化為1，因為如果初始化為0的話，會一直加都是0，當然初始化為1也是比較有歧義的，沒有什么具體物理意義；4、遍歷順序：這道題必須先遍歷物品后遍歷背包，因為求的是組合數，如果先遍歷背包后遍歷物品的話，那么每次初始化一個背包的容量，都是遍歷一次之前已經遍歷過的物品，會重復，比如會出現{1,2}和{2,1}兩種情況，所以我們要先遍歷物品后遍歷背包才可以！！！5、打印dp數組：主要用于debug和對一些情況不了解的時候！！！

代碼:

class Solution {public int change(int amount, int[] coins) {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];}
}

Leetcode 377. 組合總和 Ⅳ

題目鏈接: 組合總和 Ⅳ
自己的思路:基本和上一道題一樣！！！！只不過這道題要求的時候排列數，因為順序不同的話也是可以算做一種情況，所以我們要先遍歷背包，后遍歷物品！！！！

正確思路:

代碼:

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]) dp[j] += dp[j-nums[i]];}}return dp[target];}
}