目标和

目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //将数分为负数集与正数级，target = 正数集 - 负数集，总的值为sum  = 正数集 + 负数集
        //转为有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为(sum + target) / 2  ，有多少种方式将背包恰好填满
        //一旦正数集合确定，负数集合是剩下的数字，并且表达式 left - right的结果必定等于 target。
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //背包容量 前几个商品
        int m = nums.length;
        int n = (sum + target) / 2;
        if (n < 0) return 0;
        if ((target + sum) % 2 == 1) return 0;
        int[][] dp = new int[m+1][n+1];

        for(int i = 0;i <= n;i++){
            dp[0][i] = 0;
        }

        for(int i = 0;i <= m;i++){
            dp[i][0] = 1;
        }

        for(int i = 1;i <= m;i++){
            for(int j = 0;j <= n;j++){
                if(j < nums[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                     // 不选当前数字nums[i-1]时，仅用前i-1个数字凑出目标和j的方法数加上选定当前数字 nums[i-1]后，用前i-1个数字去凑出剩余目标 j - nums[i-1]的方法数
                    dp[i][j] =  dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[m][n];
    }
}