这道题主要是利用动态规划进行求解，优化的时候可以找规律，转化成正常的背包问题。
原题
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:1
2
3
4
5
6
7
8
9
10
11输入: 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位整数存下。
原题url：https://leetcode-cn.com/problems/target-sum/
解题
简单递归
最简单的方法就是计算出所有的可能性，如果最终结果等于目标值，则说明该情况可以。直接看一下代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28public class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
// 递归
findTargetSumWays(nums, S, 0, 0);
// 返回最终结果
return result;
}
// index : 当前计算到数组中的位置
// sum : 当前的总和
public void findTargetSumWays(int[] nums, int S, int index, int sum) {
// 遍历是否结束
if (index == nums.length) {
// 如果总和等于S，则最终结果+1
if (sum == S) {
result++;
}
return;
}
// 针对当前的数值，有加和减两种情况
findTargetSumWays(nums, S, index + 1, sum + nums[index]);
findTargetSumWays(nums, S, index + 1, sum - nums[index]);
}
}
方法很简单，但是时间复杂度太高，O(2^n)，执行用时在 java 中也只打败了31.65%，看来确实不够好。
简单的动态规划
这其实类似于背包问题，有容量要求（部分数字之和等于目标值）。首先我们来想一下状态转移方程：
我们用二维数组dp[i][j]表示用数组中的前i个元素，组成和为j的方案数。考虑第i个数nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：1
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
也可以写成递推的形式：1
2dp[i][j + nums[i]] += dp[i - 1][j]
dp[i][j - nums[i]] += dp[i - 1][j]
因为题目中提到所有数的和不超过 1000，那么 j 的最小值可以达到 -1000。在 java 中，是不允许数组的下标为负数的，因此我们需要给dp[i][j]的第二维预先增加 1000，那么新的递推关系如下：1
2dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
接下来我们看看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (S > 1000 || S < -1000) {
return 0;
}
// 求和的最大值
int max = 1000;
// 初始的数组的和不会超过1000，因此最大为1000，最小为-1000
int[][] dp = new int[nums.length][max * 2 + 1];
// 针对nums[0]，先求出第一步
dp[0][nums[0] + max] = 1;
dp[0][-nums[0] + max] += 1;
// 遍历数组
for (int i = 1; i < nums.length; i++) {
for (int sum = -max; sum <= max; sum++) {
// 如果上一步有求出和为sum，那么可以继续计算下一步
if (dp[i - 1][sum + max] > 0) {
dp[i][nums[i] + sum + max] += dp[i - 1][sum + max];
dp[i][-nums[i] + sum + max] += dp[i - 1][sum + max];
}
}
}
return dp[nums.length - 1][S + max];
}
}
提交OK，时间复杂度为O(N ∗ max)，max 代表数组中所有数字之和的最大值，执行用时在 java 中打败了58.91%，看来还有很大的提升空间。
动态规划 + 找规律
我们想一下，之所以上面的方法会涉及到 max，因为所谓的求和，并不只是加法，也可以用减法。这和我们一般理解的背包问题还是有所不同的，那么我们是否可以将本题转换成真正意义上的背包问题呢？
首先，我们可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，那么可以推导出一下关系：1
2
3
4
5
61、target = sum(P) - sum(N)
2、sum(nums) = sum(P) + sum(N)
由1可以得出：sum(P) = target + sum(N)
由2可以得出：sum(N) = sum(nums) - sum(P)
综合以上，可以得出：
sum(P) = (target + sum(nums)) / 2
因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解，这就属于正常的0-1背包问题的范畴了。需要注意target + sum(nums)必须为偶数，否则 sum(P) 就是小数了，这和题目要求的所有数都是非负整数不符。
接下来我们看看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33public class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (S > 1000 || S < -1000) {
return 0;
}
// 求出数组的和
int sumNums = 0;
for (int num : nums) {
sumNums += num;
}
// 新的目标和(sumNums + S) / 2
int newTarget = sumNums + S;
// 如果是奇数，那么无法被2整除，不符合规则
if ((newTarget & 1) == 1) {
return 0;
}
newTarget = newTarget / 2;
// 正常的背包问题，在nums中找几个数，满足和为newTarget
// dp[i]表示从数组nums找出和为i的组合情况
int[] dp = new int[newTarget + 1];
dp[0] = 1;
// 遍历数组
for (int num : nums) {
// 更新dp
for (int sum = newTarget; sum >= num; sum--) {
dp[sum] += dp[sum - num];
}
}
return dp[newTarget];
}
}
提交OK，时间复杂度是`O(n * newTarget)`，其中，` newTarget = (target + sum(nums))/2`，和前面方法中的`max`相比，`sum(nums) <= max`，如果`target > max`，也会直接返回0，因此这个方法的时间复杂度更优。
## 总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是利用动态规划，优化时可以找规律，转化成正常的背包问题。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
