头脑风暴：目标和

头脑风暴：目标和

题目

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3输出：5

解释：

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示：

数组非空，且长度不会超过 20 。初始的数组的和不会超过 1000 。保证返回的最终结果能被 32 位整数存下。

解题思路

假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = S，可以推导出：x = (S + sum) / 2。

因此，本问题就可以转化为，装满容量为x背包，有几种方法。

如果 (S + sum) / 2 不为整数，此时是没有解决方案的；并且如果目标数 S 大于 sum ,此时也是无解的。

本题需要求解的是装满背包，总共有几种方法，这就是一种组合问题了。

第一步，确定dp数组以及下标的含义：p[j] 表示：填满 j 这么大容积的包，有dp[j]种方法。

第二步，确定递推公式：求组合类问题的公式一般为 dp[j] += dp[j - nums[i]]。

第三步，dp数组初始化：在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。

第四步，确定遍历顺序：对于01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

代码实现

class Solution { public int findTargetSumWays(int[] nums, int { int sum = 0; for (int i = 0; i < nums.length; i++) sum += nums[i]; if ((target + sum) % 2 != 0) return 0; int size = (target + sum) / 2; if(size < 0) size = -size; int[] dp = new int[size + 1]; dp[0] = 1; for (int i = 0; i < nums.length; i++) { for (int j = size; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return

最后

时间复杂度：O(n × m)，n为正数个数，m为背包容量空间复杂度：O(m)，m为背包容量

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。