CODEWITHSUNDEEP
c++algorithmdynamic-programming
Frank
Frank

Reputation: 107

dynamic programming--find target sum ways in an array

I encountered a problem in leetcode, I looked other's solution which used DP, but there is something that I can't understand, hope you can give me some hints.

The problem is: Given a non-empty array containing only positive integers, find how many ways to choose some of these integers whose sum equal to target S.

The solution is:

int findTargetSumWays(vector<int>& nums, int S) 
{
    int n = nums.size();
    vector<int> dp(S+1, 0);

    dp[0] = 1;
    for(int i=0; i<n; i++)
        for(int j=S; j>=nums[i]; j--)
        //for(int j=nums[i]; j<=S; j++) //why it is wrong?
        {

            dp[j] += dp[j-nums[i]];
        }
    return dp[S];  
}

In the code, the second loop counts from S downward to nums[i], but why it cannot be counted from nums[i] upward to S? I know if count upward, the result will be much bigger than the answer, but I can't figure out the nature problem of counting upward.

any help is appreciated!

Upvotes: 1

Views: 1692

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59303

Since nums[i] is guaranteed to be positive, in the line:

dp[j] += dp[j-nums[i]]

An element of the array at a larger index is being modified based on the value of an element at a smaller index in the same array.

Because j is started high and decremented, in every iteration, it is guaranteed that the value you need to read (smaller index than j) is not one that you have already overwritten (indexes larger than j).

If, instead, you start j low and increment it, then you end up overwriting values that you will read later on the the loop. They will then have incorrect values and produce the wrong answer.

This sort of thing is a very common consideration in algorithms that operate on an array in place.

Upvotes: 1

ivan kuklin
ivan kuklin

Reputation: 140

When the second loop counts downward you count all possibilities to sum elements of array and get target S where every element of array can be taken only one time. But when second loops count upward you count possibilities where every element of array can be taken any number of times. So second number is greater or equal to first number.

Upvotes: 0

Related Questions