完全背包变体-排列和组合的循环顺序问题

排列，区分顺序：内层循环物品{1,2}，可以让3-2->1-1和3-1->2-2都计算一遍。 组合不区分顺序：外层循环物品{1,2}，只会按照物品顺序填充

总结：排列问题中，每个容量的状态更新时，允许任何物品作为最后一步加入（例如和为3时，可以是1+2或2+1），从而覆盖所有顺序；组合问题中，物品按固定顺序处理，只允许在已固定的组合末尾追加新物品，避免重复计算不同顺序的组合。

518. 零钱兑换 II 组合问题，不区分物品的组合顺序

class Solution { public: int change(int amount, vector<int>& coins) { int n=coins.size(); using ll=unsigned long long; vector<ll>dp(amount+10,0); dp[0]=1;//不需要钱的时候，只有一种方案 for(auto&& coin:coins)//内层遍历硬币会将金额j的dp覆盖 for(int j=1;j<=amount;j++){ if(j>=coin){//转移到上一个金额的方案 dp[j]=dp[j]+dp[j-coin];//dp[coins.size()-1,j]+dp[coins.size(),j-coin] } } return dp[amount]; } };

377. 组合总和 Ⅳ 排列问题，区分物品的组合顺序

class Solution { public: int combinationSum4(vector<int>& nums, int target) { using ll=unsigned long long; vector<ll>dp(target+10,0); /* 排列，区分顺序：内层循环物品{1,2}，可以让3-2->1-1和3-1->2-2都计算一遍。 组合不区分顺序：外层循环物品{1,2}，只会按照物品顺序填充 */ dp[0]=1;//0的时候只有一种组合方式 for(int j=1;j<=target;j++){ for(auto&& num:nums){ if(j>=num) dp[j]+=dp[j-num]; } } return dp[target]; } };