1. question: 目标和（中等）
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/target-sum
示例 1：
1
2
3
4
5
6
7
8
| 输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3
|
示例 2：
1
2
| 输入：nums = [1], target = 1
输出：1
|
提示：
1
2
3
4
| 1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
|
2. answers
这道题经过自己思考，终于做出来了。先讲解一下自己的做法，在对比一下题解。
首先，这道题要求所能形成target的所有组合数。因为加法和减法的存在，所以以动态规划的思想来看的话，当前元素下的target必定由两种情况组成（和爬楼梯类似）：
- 上一个元素的 target为【target - 当前元素值】的情况，表明当上一个元素的target为【target - 当前元素值】时的所有种类，因为该target + 本元素值，就是本target了，即该情况有多少种方式，那么本情况就有多少种方式
- 上一个元素的target为【target +当前元素值】的情况，表明当上一个元素的target为【target + 当前元素值】时的所有种类，因为该target - 本元素值，就是本target了，即该情况有多少种方式，那么本情况就有多少种方式
所以，可设置数组，dp[i][j]，表明，在容量J的情况下，当前元素及其前面所有元素，所能形成总和为J的表达式的种类。背包容量就是所有的总和取值范围，即[-总和, 总和]。但是为了下标，需要将其映射到正空间[0, 2*总和+1)，那么仍然需要保存背包容量为0的时刻（这里的0不是总和为0，而是不装元素的0），所以背包总范围是[0,2*总和+2)。
物品就是数组，weight就是自身nums[i]，value也是自身nums[i]。
需要初始化背包为0的情况；需要初始化仅取第一个元素的情况，注意，这里需要注意，因为target可以是正负数，因此，当target绝对值等于nums[0]时，赋值为1，表明有一种方式形成该总value。
对于情况目标值为0的情况需要特殊考虑，这里的0是下标为[sums+1]时的0，如果nums[0]也为0，此时既可以是加法，也可以是减法，即这种情况需要赋值为2。
最终返回的结果就是dp[nums.leng-1][target+sums+1]，即实际总和为target时的所有情况。代码如下所示：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| public class Solution_0121_02 {
public int findTargetSumWays(int[] nums, int target) {
int sums = 0;
for(int i: nums) sums += i;
if(Math.abs(target) > sums) return 0;
int bagSize = 2 * sums + 2;
int[][] dp = new int[nums.length][bagSize];
for (int i = 0; i < nums.length; i++) {
dp[i][0] = 0;
}
for (int i = 0; i < bagSize; i++) {
if(nums[0] == 0 && i - sums - 1 == 0) dp[0][i] = 2;
else if(nums[0] == Math.abs(i - sums - 1)) dp[0][i] = 1;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 1; j < bagSize; j++) {
int pre = 0;
int next = 0;
if(j - nums[i] >= 0) {
pre = dp[i-1][j - nums[i]];
}
if(j + nums[i] < bagSize) {
next = dp[i-1][j + nums[i]];
}
dp[i][j] = pre + next;
}
}
return dp[nums.length - 1][target + sums + 1];
}
public static void main(String[] args) {
int[] nums = {1};
int target = 2;
Solution_0121_02 s = new Solution_0121_02();
System.out.println(s.findTargetSumWays(nums, target));
}
}
|
参考了题解，其实还有另一种方式。无论表达式是什么形式，最终都可转换为A-B=target，而因为A+B=sum，显然题目就是求解AB对的数量，又因为B=(sum-target)/2，所以就是求解和为B的组合数。
因为给定的数组中均为整数，显然B一定是整数，也就是一定能整除，如果不能整除，显然是没有解的。另外，B也不能是负数，或者target<-sum，即Math.abs(target)<=sum，如果违反了这个条件也是没有解的。
那么递推公式什么样子呢？显然，和为B的组合数，如果当前元素x小于B，那么当前组合数就是和为[B-x]的组合数（因为这种组合加上当前数刚好是B，即装本元素），还有上一个元素何为B的组合数（不装本元素），是两种情况之和。
注意，可以一维动态数组来存储数值，但是初始化的时候要注意一下。
如果nums[i]=0，并且dp[j]，即j=0，也就是当前组合为0的情形，显然这时候有两种方式，即选不选都是0；
另外，如果nums[i] == j，显然是一种方式。
那么其他时候还需要赋值吗（不是0）？还有一种就是当j=0，但是nums[i]不是0的时候，显然不取该元素就行，是一种方式，即赋值为1。
代码如下所示：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| public class Solution_0121_03 {
public int findTargetSumWays(int[] nums, int target) {
int sums = 0;
for(int i: nums) sums += i;
int bagSize = sums - target;
if(bagSize % 2 != 0) return 0;
if(Math.abs(target) > sums) return 0;
bagSize = bagSize / 2;
int[] dp = new int[bagSize + 1];
for (int i = 0; i < dp.length; i++) {
if(nums[0] == 0 && i == 0) dp[i] = 2;
else if(i == 0) dp[i] = 1;
else if(nums[0] == i) dp[i] = 1;
}
for (int i = 1; i < nums.length; i++) {
for (int j = dp.length - 1; j >= 0 ; j--) {
if(j < nums[i]) dp[j] = dp[j];
else dp[j] = dp[j-nums[i]] + dp[j];
}
}
return dp[bagSize];
}
public static void main(String[] args) {
int[] nums = {9,7,0,3,9,8,6,5,7,6};
int target = 2;
Solution_0121_03 s = new Solution_0121_03();
System.out.println(s.findTargetSumWays(nums, target));
}
}
|
做到这里，似乎背包问题：
- 将问题转换为背包问题
- 确定数组含义
- 确定递推公式
- 对数组初始化
上面的每一步都很重要，但是最重要的还是如何将问题转换为背包问题。比如本题，第一种方式和第二种方式完全是两种不同的思维。
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
