4ms C++ DP solution with comments


  • 0
    S

    Similar to the problem "Stairs" we are looking for a number of combination of lesser target. If its complicated for you now - try to solve Stairs first.

        {
            // init all previous targets with 0
            vector<int> prevTargets(target+1, 0);
            
            // dynamic programming: memo the previous target combinations
            for (int xT=1; xT<=target; ++xT)
            {
                for (int i=0; i<nums.size(); ++i)
                {
                    
                    // if current target is equal to the number - its +1 combination
                    if (xT == nums[i])
                        prevTargets[xT] += 1;
                        
                    // if current target - current number is more than 0 - add this combination too
                    if ((xT - nums[i]) >= 0)
                        prevTargets[xT] += prevTargets[xT - nums[i]];
    
                }
            }
            
            // return the last (desired) combination as a result
            return prevTargets.back();
        }```

Log in to reply
 

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