LeetCode DayDynamic Programming Part 4

    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];       

    }