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

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