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

排列，区分顺序：内层循环物品{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];}
};