494. 目标和

题目链接

代码随想录

分析

动态规划

这道题有点困难。我一开始没想到思路，但是后面找到了正确的 dp 的定义，然后就很顺了。

首先因为数组的所有成员都是非负数，所以只要做过 416. 分割等和子集 大概就是知道，这个操作其实是把整个数组的数字分成两拨，然后用一波的和减去另一波的和，得到的差值是 target，这个其实是在求从数组中找出一些数字，这些数字的和为 (sum+target)/2，典型的背包问题。

但是，这又不是典型的背包问题，题目中要我们求的，其实是两拨数字的和差值等于 target 的不同表达式的数目。注意求的是数目，而不是最大值。

KM-46. 携带研究材料 中，我们求的是将多个物品放入有限容量的背包中，物品的总价值的最大值是多少。而这个题，求的是，将多个物品放入指定容量的背包中，刚好把背包填满，有多少种填法。我们在之前做动态规划的时候的经验就是，直接根据最终要求出的数字的定义来定义 dp 数组，比如 343. 整数拆分，这里我们也是这样做。

定义 dp[i][j] 表示从索引 0 到索引 i 种选出元素，使得其和等于 j 的组合的种类。

同样的分两种情况讨论，选择物品 i 和不选择物品 i：

• 不选择物品 i。有 dp[i][j]=dp[i-1][j]; 种组合。
• 选择物品 i，有 dp[i][j]=dp[i-1][j-nums[i]]; 种组合。

那 dp[i][j] 总共有多少种组合呢？这两者的和 dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];，这就是状态转移方程。

然后就是初始化，我们需要初始化 dp[0][j] 和 dp[i][0],

• dp[0][j] 很简单，只有与 nums[0] 相等的 j 对应的 dp[0][j] 等于 1，其他都等于 0，
• dp[i][0] 有点复杂，这是这个问题的难点，我们分情况讨论，
  • 如果从物品 0 到物品 i 没有一个元素是 0，那么一个元素都不取，也是一种满足 j 等于 0 的方法，dp[i][0]=1，也就是 $2^0$，
  • 如果从物品 0 到物品 i 有 n 个元素是 0，那么有多少种方法呢满足和为 0 呢？ $C_n^1+...+C_n^n=2^n-1$ ,加上一个元素都不取的方案，刚好就是 $2^n$，参考 排列(Arrangment)和组合(combination)#组合公式Ⅲ
  • 也就是说 dp[i][0] 实际上就等于 $2^n$ 其中 n 为从物品 0 到物品 i 中 0 的个数。我们初始化的时候，可以不需要直接使用 Math.pow(base, exponent); 函数，而是先初始化一个 count 为 1，然后碰到 0 就将 count 自增为自己的 2 倍，然后将 count 赋值给 dp[i][0]。

然后遍历方式，就是外层从索引 1 到索引 i 遍历数字，内层从 1 开始从小达到遍历和。

此外注意点，target 可能不是合法的，可能无法达到，无法达到就直接返回 0。

• 如果 target 大于 sum，或者 target 小于 sum*-1，那 target 是无法达到的，因为 nums 的元素都是非负的，现在将所有元素都为正数，或者所有元素都为负数都不行无法达到 target，因此需要直接返回 0。
• 如果 (sum+target)/2 有余数，即 (sum+target)%2!=0，则说明无法分成两拨且两拨的和的差值为 target 的。此时可直接返回 0。

优化

老规矩，用一纬 dp 数组能否解决问题，答案是可以。

定义 dp[j] 为将多个物品塞到容量为 j 的背包中刚好塞满的方式的个数。

然后状态转移方程经过简化就是 dp[j] = dp[j] + dp[j-nums[i]];。

以上其实都还比较容易想到，这道题最难的，其实是 dp 数组的初始化。根据 dp 数组的定义，dp[0] 应该是多少，在 KM-46. 携带研究材料#优化 中我们就讨论过，我们是从 i=0 的时候开始遍历，所以我们实际上是在没有选择任何物品的场景下初始化 dp 数组，我们可以假设物品 0 上面还有一行，就是啥物品都不放，那么可想而知，此时只有 dp[0] = 1; 其他都为 0，因为当 j=0 的时候，什么物品都不选也可以实现，（废话，也没物品给你选），

我们可以发现，dp[j] = dp[j]+dp[j-nums[i]] 如果 nums[i]=0，实际上就是 dp[j]*2，跟二维的情况是一样的。

一维 dp 数组的遍历方式，跟 KM-46. 携带研究材料#优化 一样，外层遍历物品，内层遍历背包容量，容量是从大到小遍历，遍历到 nums[i] 为止。这里就不赘述了。

以上过程是我自己的思维过程，具体的详细的推导过程，看 代码随想录二维 dp，代码随想录一维 dp

贪心

这个题跟 40. 组合总和 II 很像，我看到本题的时候，脑子里闪过的也是组合，但是 40. 组合总和 II 是要求我们把所有的组合的情况求出来，而不仅仅是求出组合的个数，所以这道题还是只能用动态规划来做。

解题

二维 dp

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        // 选出一部分数，使其和等于 x，总共有多少种方法。
        int sum = 0;
        for (int ele : nums) {
            sum += ele;
        }
        if(target>sum || target<sum*-1){
            return 0;
        }
        if((sum + target) % 2 !=0){
            return 0;
        }
        int eleSum = (sum + target) / 2;
        // System.out.println(eleSum);
        // dp[i][j] 表示从索引0到索引i种选出元素，其和等于 i的组合的种类的种类
        int[][] dp = new int[nums.length][eleSum + 1];
        for (int j = 1; j <= eleSum; j++) {
            if (nums[0] == j) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }
        // 不能简单的的将dp[i][0] 全部设置成1，因为nums的值可能为0，有一个为 0 ，组合的数量就得乘以2，因此，
        // dp[i][0] 的值 ，等于 从物品0到物品i种0的个数的二次幂
        int count = 1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                count*=2;
            }
            dp[i][0] = count;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= eleSum; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // for (int[] s : dp) {
        //     System.out.println(Arrays.toString(s));
        // }
        return dp[nums.length - 1][eleSum];
    }

}

一维 dp

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        // 选出一部分数，使其和等于 x，总共有多少种方法。
        int sum = 0;
        for (int ele : nums) {
            sum += ele;
        }
        if(target>sum || target<sum*-1){
            return 0;
        }
        if((sum + target) % 2 !=0){
            return 0;
        }
        int eleSum = (sum + target) / 2;
        int[] dp = new int[eleSum + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = eleSum; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
            // System.out.println(Arrays.toString(dp));
        }
        return dp[eleSum];
    }

}

public int findTargetSumWays(int[] nums, int target) {
  int sum = 0;
  for(int num:nums){
    sum += num;
  }
  // target 大于 sum，无解
  if(target>sum){
    return 0;
  }
  //sum+target 不能整除，无解
  if((sum+target)%2!=0){
    return 0;
  }
  int targetSize = (sum+target)/2;
  int[] dp = new int[targetSize+1];
  // 注意 dp[0]什么都不放，也是一种方式，
  // 这跟把价值为0的元素放进去，不同。
  dp[0]=1;
  for(int i=0;i<nums.length;i++){
    for(int j=targetSize;j>=nums[i];j--){
      dp[j] = dp[j]+dp[j-nums[i]];
    }
  }
  return dp[targetSize];
}

相关题

39. 组合总和

1049. 最后一块石头的重量 II

416. 分割等和子集

完全背包：

518. 零钱兑换 II