3ms C++ 01 knapsack problem clean and concise


  • 0
    T
    /*
        01 knapsack problem
        f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
    */
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target)
        {
            int f[target+10]={0};
            int ln=nums.size();
            f[0]=1;
            for(int v=1;v<=target;v++)
                for(int i=0;i<ln;i++)
                    if (v>=nums[i])
                        f[v]+=f[v-nums[i]];
            return f[target];
        }
    
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.