4ms C++ DP solution with comments

  • 0

    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.