动态规划(01背包组合问题):力扣494目标和

 public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if ((sum+target)%2==1) return 0; //如果除2有余数说明没有组合,只求正数部分或负数部分
        if (Math.abs(target)>sum) return 0; //如果目标值的绝对值都大于sum,那么怎么都凑不出来组合了
        int bagSize=(sum+target)/2; //背包容量
        int []dp=new int[bagSize+1];
        Arrays.fill(dp,0);
        dp[0]=1;//初始化dp[0]=1

        for (int i = 0; i <nums.length ; i++) {
            for (int j = bagSize; j >=nums[i] ; j--) {
                //01背包的组合问题递推公式与之前的不同,组合问题的dp公式是累加
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }