完全背包問題：
完全背包與01背包不同的地方在于完全背包可以將一個物品放無數(shù)次且轨，由此可得在動態(tài)規(guī)劃5步中浮声，遍歷順序就有所改變，之前是先遍歷物品旋奢，后遍歷背包泳挥，而且背包是倒序遍歷，此時背包的遍歷是正序至朗，而且無論是先遍歷背包還是物品都可以屉符。
518.?零錢兌換 II
思路：
這道題的思路與第494題一致，都是問有多少種解法，只是本題物品的數(shù)量可以取多次筑煮。dp[i]：容量為i的背包有dp[i]中裝法辛蚊，遞推關(guān)系：與第494題一致粤蝎，dp[i]+=dp[i-nums[i]]真仲；初始化：dp[0]=1；遍歷順序：如果先遍歷物品再遍歷背包初澎，代碼如下：
for(inti=0;i<coins.size();i++)
{for(intj=coins[i];j<=amount;j++)
????{dp[j]+=dp[j-coins[i]];}}
在內(nèi)層for循環(huán)中秸应，j的起始值為coins[i]，然后遞增碑宴，這就排除了比coins[i]小的背包软啼，此時求的是組合數(shù)。如果先遍歷背包延柠，再遍歷物品祸挪，代碼如下：
for(intj=0;j<=amount;j++)
{for(inti=0;i<coins.size();i++)
{if(j-coins[i]>=0)dp[j]+=dp[j-coins[i]];}}
此時求的是排列數(shù)。
代碼：
class Solution {
public:
? ? int change(int amount, vector<int>& coins) {
? ? ? ? vector<int> dp(amount+1,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.?組合總和 Ⅳ
思路：
這道題和第518題思路一致贞间，不同的是這道題求得是排列贿条，所以在遍歷順序上應(yīng)該是先背包后物品。
代碼：
class Solution {
public:
? ? int combinationSum4(vector<int>& nums, int target) {
? ? ? ? vector<int> dp(target+1,0);
? ? ? ? dp[0]=1;
? ? ? ? for(int j=0;j<=target;j++)
? ? ? ? {
? ? ? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]])
? ? ? ? ? ? ? ? dp[j]+=dp[j-nums[i]];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[target];
? ? }
};
