LeetCode Day31 Dynamic Programming Part 4

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
Original Page

Even though the backtracking is useful here we can use dynamic programming to solve this problem to achieve less time complexity.

    public int findTargetSumWays(int[] nums, int target) {
        /**
        sum(neg) + sum(pos) = sum(nums);
        sum(pos) - sum(neg) = target;
        sum(pos) = (sum(nums) + target) / 2 
         */
        int sum = Arrays.stream(nums).sum();
        // that means the sum of the positive number is invalid, because the nums do not conclude float
        if((sum+target)%2 != 0|| Math.abs(target) > sum){
            return 0;
        }

        // here we find the summary of the positive numbers
        int pos = (sum + target) >>1;

        // dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods   
        int[][] dp = new int[nums.length+1][pos+1];

        // if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
        dp[0][0] = 1;

        // if(nums[0] <= pos){
        //     dp[0][nums[0]] = 1;
        // }

        for(int i = 1; i <= nums.length; i++){
            for(int j=0; j<=pos; j++){
                if(nums[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }
            }
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[nums.length][pos];       

    }

Note

1, init the dp array is important especially here it is important to find out that the meaning of 0