第一种思路：
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 代表前i个数组合成j的方案数，由于数可能为负数，这里设置1000的偏移量，将
[
−
1000
,
1000
]
[-1000, 1000]
[−1000,1000]转化为
[
0
,
2000
]
[0, 2000]
[0,2000]。每次转移有2种状态
−
n
u
m
s
[
i
]
和
+
n
u
m
s
[
i
]
-nums[i] 和 +nums[i]
−nums[i]和+nums[i] 分别统计2种状态的所有结果即可。时间复杂度
O
(
n
m
)
O(nm)
O(nm),
n
为
n
u
m
s
.
s
i
z
e
(
)
,
m
为
s
u
m
(
n
u
m
s
)
n为nums.size(),m为sum(nums)
n为nums.size(),m为sum(nums)。空间复杂度为
O
(
n
m
)
O(nm)
O(nm)
第二种思路：
s
u
m
=
n
u
m
s
sum = nums
sum=nums的元素之和，
p
p
p为所有为-号的元素之和，那么所有为+号的元素之和为
s
u
m
−
p
sum - p
sum−p,最终
t
a
r
g
e
t
=
(
s
u
m
−
p
)
−
p
=
s
u
m
−
2
p
target = (sum - p) - p = sum - 2p
target=(sum−p)−p=sum−2p,所以可以推出p的表达式为
p
=
s
u
m
−
t
a
r
g
e
t
2
p=\frac{sum - target}{2}
p=2sum−target, 那么问题就转化为01背包求方案数。注意特殊情况，若target大于sum，那么直接返回0；若sum-target为奇数，那么也直接返回0，因为
2
p
=
s
u
m
−
t
a
r
g
e
t
2p=sum-target
2p=sum−target，sum-target必为非负偶数。时间复杂度为
O
(
n
p
)
O(np)
O(np) 空间复杂度为
O
(
p
)
O(p)
O(p)
三 、代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
//vector<vector<int>> dp(n + 1, vector<int>(2001));
int dp[21][2001] = {0};
dp[0][1000] = 1;
for (int i = 1; i <= nums.size(); i++) {
int t = nums[i - 1];
for (int j = 0; j <= 2000; j++) {
if (j + t <= 2000) dp[i][j + t] += dp[i - 1][j];
if (j - t >= 0) dp[i][j - t] += dp[i - 1][j];
}
/*
for (int j = t; j <= 2000 - t; j++) {
dp[i][j + t] += dp[i - 1][j];
dp[i][j - t] += dp[i - 1][j];
}
*/
}
return dp[n][target + 1000];
}
};
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size(), sum = 0, p;
for (int i = 0; i < n; i++) sum += nums[i];
p = (sum - target);
if (p < 0 || p % 2 == 1) return 0; //sum-target 必须是非负偶数,因为2p = sum - target
p /= 2;
int dp[1001] = {0};
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = p; j >= nums[i - 1]; j--) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp[p];
}
};