一、题目描述
给你一个非负整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-'，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。示例 1：
输入：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：
输入：nums = [1], target = 1 输出：1
二、解题思路（动态规划）
算法思路：分析问题，将问题转化为背包类型的问题。
设我们最终选取的结果中，前面要加 + 号的数字之和为 a ，前面要加 - 号的数字之和为 b ，整个数组 的总和为 sum ，于是我们有： a + b = sum ，a - b = target .
上面两个式子消去 b 之后，可以得到 a = (sum + target) / 2。
也就是说，我们仅需在 nums 数组中选择一些数，将它们凑成和为 (sum + target) / 2 即可。
1、状态表示
dp[i][j] 表示：在前 i 个数中选，总和正好等于 j ，一共有多少种选法。
2、状态转移方程
根据最后一个位置的元素，结合题目的要求， 有选择最后一个元素或者不选择最后一个元素两种策略：
（1）不选 nums[i] ： 那么凑成总和 j 的总方案，就要看在前 i - 1 个元素中选，凑 成总和为 j 的方案数。根据状态表示，此时 dp[i][j] = dp[i - 1][j] ；
（2）选择 nums[i] ： 这种情况下是 有前提条件的，即 nums[i] <= j 。
那么我们能够凑成总和为 j 的方案数，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。 根据状态表示，此时 dp[i][j] = dp[i - 1][j - nums[i]].
综上所述， 两种情况如果存在的话，应该要累加在一起。 因此，状态转移方程为：
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] + dp[i - 1][j - nums[i - 1]]
3、初始化
由于需要用到上一行的数据，因此我们可以先把第一行初始化。
第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = 1。
4、填表顺序
从上往下填写每一行，每一行的顺序是无所谓的。
5、返回值
根据状态表示，返回 dp[n][aim] 的值。
其中 n 表示数组的大小， aim 表示要凑的目标和。
三、代码
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
int sum = 0;
for(int x : nums) {
sum += x;
}
int aim = (sum + target) / 2;
//要找的aim是大于0的，小于0直接返回
if(aim < 0 || (sum + target) % 2 == 1) {
return 0;
}
int[][] dp = new int[n+1][aim+1];
//初始化
dp[0][0] = 1;
//填表
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= aim; j++) {
dp[i][j] = dp[i-1][j];
if(j >= nums[i-1]) {
dp[i][j] = dp[i][j]+dp[i-1][j-nums[i-1]];
}
}
}
//返回值
return dp[n][aim];
}四、优化
空间优化：
所有的「背包问题」，都可以进行空间上的优化。
对于 01背包类型的，我们的优化策略是：
- 删掉第一维；
- 修改第二层循环的遍历顺序即可
代码：
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
int sum = 0;
for(int x : nums) {
sum += x;
}
int aim = (sum + target) / 2;
if(aim < 0 || (sum + target) % 2 == 1) {
return 0;
}
int[] dp = new int[aim+1];
//初始化
dp[0] = 1;
//填表，注意填表顺序
for(int i = 1; i <= n; i++) {
for(int j = aim; j >= nums[i-1]; j--) {
dp[j] = dp[j]+dp[j-nums[i-1]];
}
}
//返回值
return dp[aim];
}
