Target Sum dp

• Description
• Solution

Description

Leetcode 494. Target Sum
You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Solution

class Solution
{
public:
    int lastStoneWeightII(vector<int> &stones)
    {
        // to get the minimum weight of last stone, we can try to segregate stones into two equal weight subsets

        // 1.make an example
        // 2.consider exceptions
        if (stones.size() == 1)
            return stones[0];

        // 3.find target capacity
        int sum = 0;
        for (int a : stones)
        {
            sum += a;
        }

        int target = sum / 2; // try to find subset with a sum close to target

        // 4.dp[j]: for subsets with a capacity of j, the actual maximum sum of elements is dp[j]
        vector<int> dp(target + 1, 0);

        // 5.equation and traversal
        for (int i = 0; i < stones.size(); i++)
        {
            for (int j = target; j >= stones[i]; --j)
            {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        int subset1 = dp[target];
        int subset2 = sum - subset1;
        return (subset2 - subset1);
    }
};