leetcode 377. 組合せ合計IV

問題を解く構想.
完全にリュックカウントの構想は書かないで、これはリュックサックを理解すれば、直接打つことができるからです.この問題はc++で書かれており、unsigned long longで保存する必要があります.データ量が多い.ここでは完全リュックサックの書き方をご紹介します.実はこの問題は少し特殊で、順序の異なる組み合わせも1組計算しなければならないので、列挙の順序はfor(int j=1;j<=target;j++)for(int i=0;i
順序要求がなければ(1,2,1)と(1,1,2)は同じである.逆に書く.
コード#コード#

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n=nums.size();
        int dp[target+3];
        unsigned long long f[target+3];
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int j=1;j<=target;j++)
        {
            for(int i=0;i<n;i++)
            {
                if(j<nums[i]) continue;
                if(dp[j-nums[i]]+nums[i]>=dp[j])
                {
                    dp[j]=dp[j-nums[i]]+nums[i];
                    f[j]+=f[j-nums[i]];
                    //cout<
                }
            }
        }
       // cout<
        return f[target];
    }
};