---

518.零錢兌換II

題目鏈接

思路

1. 確定dp數組（dp table）以及下標的含義
   dp[j]：組合元素和為j的組合方式
2. 確定遞推公式
   題目不是選取最優解，而是求路徑總和，則取不同數字的零錢coin[i]時都有dp[j-coin[i]]種方法，
   則dp[j]=dp[j-coin[i]]
3. dp數組如何初始化
   后臺題目要求是dp[0]=1，這里題目沒給出準確的說法
4. 確定遍歷順序
   外層for循環從前往后，內層for循環也是從前往后
   這和01背包完全不同，根本原因就是這里的錢每個面額的數量都沒有限制，所以可以重復選取
   但外層for循環和內存for循環不可以調換，因為現在是先遍歷錢，錢是不會出現{5,1}和{1,5}這樣的重復現象的；但如果錢變成內層for循環的話，就可以重復選取，這就是后面那道題的排列問題
5. 舉例推導dp數組

代碼實現

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(10010,0);dp[0]=1;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
};

---

377. 組合總和 Ⅳ

題目鏈接

思路

這道題就是排列問題

1. 確定dp數組（dp table）以及下標的含義
   dp[j]：組合元素和為j的組合方式
2. 確定遞推公式
   題目不是選取最優解，而是求路徑總和，則取不同數字的零錢coin[j]時都有dp[i-coin[j]]種方法，
   則dp[i]=dp[i-coin[j]]
3. dp數組如何初始化
   后臺題目要求是dp[0]=1，這里題目沒給出準確的說法
4. 確定遍歷順序
   外層for循環從前往后，內層for循環也是從前往后
   這就是排列問題，{5,1}和{1,5}都是正確結果。而錢變成內層for循環的話，就可以重復選取。先遍歷背包容量，當容量允許裝入背包，就可以累加記錄方法種類，代碼實現和上一道題差不多，只是換了內外層的遍歷
5. 舉例推導dp數組

這里有一個dp[i]<INT_MAX-dp[i-nums[j]]操作，因為測試數據比較大時累加結果可能超過了INT_MAX，為了保證數據不溢出，就需要判斷dp[i]+dp[i-nums[j]]<INT_MAX是否成立，而dp[i]+dp[i-nums[j]]可能還是會溢出，所以只能用減法寫

代碼實現

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(10010,0);dp[0]=1;for(int i=0;i<=target;i++){for(int j=0;j<nums.size();j++){if(i>=nums[j]&&dp[i]<INT_MAX-dp[i-nums[j]])dp[i]+=dp[i-nums[j]];}}return dp[target];}
};

---