494. 目标和

依旧是背包问题,这题是01背包,因为数字不允许重复使用

class Solution { public int findTargetSumWays(int[] nums, int target) { //先计算总和 int sum = 0; for (int num : nums) { sum += num; } //计算差值 int diff = sum - target; //如果目标值大于总和,或者要组合的数不是整数,返回0 if (diff < 0 || diff % 2 != 0) { return 0; } //neg就是我们要找的要加负号的数的和 int neg = diff / 2; int[] dp = new int[neg+1]; dp[0] = 1; for (int num : nums){ for(int j = neg; j>=num ; j--){ dp[j] += dp[j-num]; } } return dp[neg]; } }